Number of Valid Words in a Sentence

easy string

Problem

A valid word: contains only lowercase letters, hyphens and punctuation '!' ',' '.'; contains at most one hyphen, and if present, it must be surrounded by lowercase letters; contains at most one of '!' ',' '.', and only at the end. Count how many tokens in a sentence are valid words.

Inputsentence = "cat and dog"

Output3

Tokens split on whitespace: ["cat", "and", "dog"]. Empty tokens are dropped.

sentence

def count_valid_words(s):
    def is_valid(t):
        hy = 0
        for i, c in enumerate(t):
            if c.isdigit():
                return False
            if c == '-':
                hy += 1
                if hy > 1 or i == 0 or i == len(t)-1 \
                   or not t[i-1].isalpha() or not t[i+1].isalpha():
                    return False
            elif c in '!,.' and i != len(t)-1:
                return False
        return True
    return sum(1 for tok in s.split() if is_valid(tok))

function countValidWords(s) {
  const isLet = c => c >= 'a' && c <= 'z';
  const isValid = t => {
    let hy = 0;
    for (let i = 0; i < t.length; i++) {
      const c = t[i];
      if (c >= '0' && c <= '9') return false;
      if (c === '-') {
        if (++hy > 1 || i === 0 || i === t.length-1
            || !isLet(t[i-1]) || !isLet(t[i+1])) return false;
      } else if ("!,.".includes(c) && i !== t.length-1) {
        return false;
      }
    }
    return true;
  };
  return s.split(/\s+/).filter(Boolean).filter(isValid).length;
}

class Solution {
    public int countValidWords(String s) {
        int count = 0;
        for (String t : s.trim().split("\\s+")) {
            if (t.isEmpty()) continue;
            if (isValid(t)) count++;
        }
        return count;
    }
    private boolean isValid(String t) {
        int hy = 0;
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (Character.isDigit(c)) return false;
            if (c == '-') {
                if (++hy > 1 || i == 0 || i == t.length()-1
                    || !Character.isLetter(t.charAt(i-1))
                    || !Character.isLetter(t.charAt(i+1))) return false;
            } else if ((c=='!'||c==','||c=='.') && i != t.length()-1) {
                return false;
            }
        }
        return true;
    }
}

bool valid(const string& t) {
    int hy = 0, n = t.size();
    for (int i = 0; i < n; i++) {
        char c = t[i];
        if (isdigit(c)) return false;
        if (c == '-') {
            if (++hy > 1 || i == 0 || i == n-1
                || !isalpha(t[i-1]) || !isalpha(t[i+1])) return false;
        } else if ((c=='!'||c==','||c=='.') && i != n-1) {
            return false;
        }
    }
    return true;
}
int countValidWords(string s) {
    int count = 0, n = s.size(), i = 0;
    while (i < n) {
        while (i < n && s[i] == ' ') i++;
        int j = i;
        while (j < n && s[j] != ' ') j++;
        if (j > i && valid(s.substr(i, j-i))) count++;
        i = j;
    }
    return count;
}

Explanation

This is a parsing problem: split the sentence into tokens, then check each token against a few simple rules and count how many pass. The clever part is that all the rules can be verified in a single left-to-right scan of each token.

First we split on whitespace (and drop empty pieces). Then for each token, is_valid walks the characters tracking hy, the number of hyphens seen so far.

Three things make a token invalid. A digit anywhere fails immediately. A hyphen - fails if it is the second hyphen (hy > 1), or sits at the very start or end, or is not flanked by letters on both sides. A punctuation mark from !,. fails if it appears anywhere except the last position.

If the scan finishes without hitting any of those, the token is a valid word and we add 1 to the total.

Example: "cat and dog" splits into ["cat", "and", "dog"] (the double space yields no empty token). None contain digits, hyphens, or misplaced punctuation, so all three are valid and the answer is 3.

Time: O(n) Space: O(n)