# Number of Valid Words in a Sentence
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-valid-words-in-a-sentence)
Canonical: https://scaleengineer.com/dsa/problems/number-of-valid-words-in-a-sentence
**Data structures:** String
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco)
---
## Problem
A sentence consists of lowercase letters (`'a'` to `'z'`), digits (`'0'` to `'9'`), hyphens (`'-'`), punctuation marks (`'!'`, `'.'`, and `','`), and spaces (`' '`) only. Each sentence can be broken down into **one or more tokens** separated by one or more spaces `' '`.

A token is a valid word if **all three** of the following are true:

* It only contains lowercase letters, hyphens, and/or punctuation (**no** digits).
* There is **at most one** hyphen `'-'`. If present, it **must** be surrounded by lowercase characters (`"a-b"` is valid, but `"-ab"` and `"ab-"` are not valid).
* There is **at most one** punctuation mark. If present, it **must** be at the **end** of the token (`"ab,"`, `"cd!"`, and `"."` are valid, but `"a!b"` and `"c.,"` are not valid).

Examples of valid words include `"a-b."`, `"afad"`, `"ba-c"`, `"a!"`, and `"!"`.

Given a string `sentence`, return _the **number** of valid words in_ `sentence`.

**Example 1:**

**Input:** sentence = "cat and  dog"
**Output:** 3
**Explanation:** The valid words in the sentence are "cat", "and", and "dog".

**Example 2:**

**Input:** sentence = "!this  1-s b8d!"
**Output:** 0
**Explanation:** There are no valid words in the sentence.
"!this" is invalid because it starts with a punctuation mark.
"1-s" and "b8d" are invalid because they contain digits.

**Example 3:**

**Input:** sentence = "alice and  bob are playing stone-game10"
**Output:** 5
**Explanation:** The valid words in the sentence are "alice", "and", "bob", "are", and "playing".
"stone-game10" is invalid because it contains digits.

**Constraints:**

* `1 <= sentence.length <= 1000`
* `sentence` only contains lowercase English letters, digits, `' '`, `'-'`, `'!'`, `'.'`, and `','`.
* There will be at least `1` token.

# Approaches
## Manual Validation after Splitting
This approach first splits the sentence into individual tokens based on spaces. Then, it iterates through each token and manually checks if it conforms to the three rules for a valid word using a helper function.
**Time:** O(N), where N is the length of the sentence. Splitting the sentence takes O(N) time. Then we iterate through each token. Since we visit each character of the sentence once across all tokens, the total time for validation is also O(N). · **Space:** O(N), where N is the length of the sentence. The `split` method creates an array of tokens, which in the worst case (e.g., "a b c d...") can take up space proportional to the original sentence length.
**Pros:** The logic is very explicit and easy to follow.; Each validation rule is checked separately, making the code straightforward to debug.
**Cons:** Can be more verbose than other solutions.; Uses O(N) extra space to store all tokens at once, which is suboptimal for very long sentences.
### Explanation
First, the input `sentence` is trimmed to remove leading/trailing spaces and then split into an array of strings using one or more spaces as the delimiter (`"\\s+"`). This gives us all the potential tokens. We initialize a counter for valid words to zero. We then loop through each `token` in the array. For each non-empty token, we call a helper function, `isValid(token)`, to determine if it's a valid word. The `isValid(token)` function implements the validation logic by iterating through the characters of the token and checking each of the problem's conditions explicitly. If `isValid(token)` returns true, we increment our counter. Finally, we return the total count.

```java
class Solution {
    public int countValidWords(String sentence) {
        String[] tokens = sentence.trim().split("\\s+");
        int count = 0;
        for (String token : tokens) {
            if (isValid(token)) {
                count++;
            }
        }
        return count;
    }

    private boolean isValid(String token) {
        if (token.isEmpty()) {
            return false;
        }
        int n = token.length();
        int hyphenCount = 0;
        
        for (int i = 0; i < n; i++) {
            char c = token.charAt(i);

            if (Character.isDigit(c)) {
                return false;
            }

            if (c == '-') {
                hyphenCount++;
                if (hyphenCount > 1) {
                    return false;
                }
                if (i == 0 || i == n - 1) {
                    return false;
                }
                if (!Character.isLetter(token.charAt(i - 1)) || !Character.isLetter(token.charAt(i + 1))) {
                    return false;
                }
            }

            if (c == '!' || c == '.' || c == ',') {
                if (i != n - 1) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Split the `sentence` into an array of `tokens` using one or more spaces as the delimiter.
- Initialize `validWordCount = 0`.
- For each `token` in the `tokens` array:
  - If the `token` is not empty, call a helper function `isValid(token)`.
  - If `isValid(token)` returns `true`, increment `validWordCount`.
- Return `validWordCount`.

**`isValid(token)` Algorithm:**
- Check for digits. If any are found, return `false`.
- Count hyphens. If more than one, return `false`. If one exists, check that it's not at the start or end and is surrounded by letters.
- Check for punctuation. If any punctuation exists, ensure it's the last character of the token and that there's only one.

## Regular Expression Matching
This approach leverages the power of regular expressions to define a pattern for a valid word. After splitting the sentence into tokens, each token is matched against this pattern.
**Time:** O(N), where N is the length of the sentence. Splitting takes O(N). Regex matching on each token takes time proportional to the token's length. The total time is dominated by scanning the sentence, resulting in O(N) complexity. · **Space:** O(N), where N is the length of the sentence. Similar to the manual approach, splitting the sentence creates an array of tokens that can occupy O(N) space.
**Pros:** Very concise and expressive, as the validation logic is captured in a single pattern.; Can be easier to modify if the rules for a valid word change.
**Cons:** Regular expressions can be hard to read and debug for those not familiar with them.; Performance might have a higher constant factor compared to a direct manual check due to the overhead of the regex engine.; Still uses O(N) extra space for the tokens.
### Explanation
The core of this approach is to construct a single regular expression that encapsulates all three rules for a valid word. The regex pattern for a valid word can be defined as `^([a-z]+(-[a-z]+)?)?[!.,]?$`. This pattern ensures that the token contains no digits, has at most one hyphen correctly placed between letters, and at most one punctuation mark at the very end. The algorithm first splits the sentence into tokens, then iterates through them, using the `matches()` method to check if each token conforms to the regex. The number of matching tokens is the result.

```java
import java.util.regex.Pattern;

class Solution {
    public int countValidWords(String sentence) {
        String regex = "^([a-z]+(-[a-z]+)?)?[!.,]?$";
        Pattern pattern = Pattern.compile(regex);

        String[] tokens = sentence.trim().split("\\s+");
        int count = 0;
        for (String token : tokens) {
            if (!token.isEmpty() && pattern.matcher(token).matches()) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Define the regex pattern for a valid word: `^([a-z]+(-[a-z]+)?)?[!.,]?$`.
- Split the `sentence` into an array of `tokens` using spaces as delimiters.
- Initialize `validWordCount = 0`.
- For each `token` in `tokens`:
  - If the `token` is not empty and matches the regex pattern, increment `validWordCount`.
- Return `validWordCount`.

## Optimized Single Pass Scan
This is the most efficient approach in terms of space. Instead of splitting the sentence into an array of tokens first, it processes the sentence in a single pass. It identifies token boundaries on the fly and validates each token as it's found, avoiding the need to store all tokens in memory simultaneously.
**Time:** O(N), where N is the length of the sentence. We iterate through the sentence once to find tokens. The `substring` operation and the validation for each token together process each character of the sentence a constant number of times. · **Space:** O(L), where L is the maximum length of a token in the sentence. This is because we only store one token at a time for validation. In the worst case, L can be O(N) if the sentence has no spaces, but on average, it's much smaller.
**Pros:** Most space-efficient approach, using O(L) instead of O(N) space.; Avoids the overhead of creating a large intermediate array of strings.
**Cons:** The logic for manually tokenizing (managing `start` and `end` pointers) is slightly more complex than simply calling `split()`.
### Explanation
This method avoids the O(N) space complexity of the previous approaches by not creating an intermediate array of all tokens. It iterates through the sentence using indices to identify tokens one by one. We use a `start` index to mark the beginning of a potential token and an `end` index to find its end (at a space or the end of the sentence). Once a token is demarcated, we extract the substring and pass it to the same `isValid` validation function. This process continues until the entire sentence has been scanned, using only space for one token at a time.

```java
class Solution {
    public int countValidWords(String sentence) {
        int count = 0;
        int n = sentence.length();
        int start = 0;
        
        for (int i = 0; i < n; i++) {
            // Skip leading spaces for the next token
            while (start < n && sentence.charAt(start) == ' ') {
                start++;
            }
            if (start >= n) break;

            // Find the end of the current token
            int end = start;
            while (end < n && sentence.charAt(end) != ' ') {
                end++;
            }
            
            String token = sentence.substring(start, end);
            if (isValid(token)) {
                count++;
            }
            
            // Move start to the beginning of the next potential token
            start = end + 1;
            i = end;
        }
        return count;
    }

    private boolean isValid(String token) {
        if (token.isEmpty()) return false;
        int n = token.length();
        int hyphenCount = 0;
        for (int i = 0; i < n; i++) {
            char c = token.charAt(i);
            if (Character.isDigit(c)) return false;
            if (c == '-') {
                hyphenCount++;
                if (hyphenCount > 1) return false;
                if (i == 0 || i == n - 1) return false;
                if (!Character.isLetter(token.charAt(i - 1)) || !Character.isLetter(token.charAt(i + 1))) return false;
            }
            if ((c == '!' || c == '.' || c == ',') && i != n - 1) return false;
        }
        return true;
    }
}
```
### Algorithm
- Initialize `validWordCount = 0` and pointers/indices `start` and `end`.
- Iterate through the sentence to find token boundaries (spaces or end of string).
- For each substring identified as a token:
  - If the token is not empty, extract it.
  - Validate the token using a helper function `isValid()` (the same as in the first approach).
  - If valid, increment `validWordCount`.
- After validating a token, advance the `start` pointer past the current token and any subsequent spaces.
- Return `validWordCount`.

# Solutions
### Java

```java
class Solution { public int countValidWords ( String sentence ) { int ans = 0 ; for ( String token : sentence . split ( " " )) { if ( check ( token )) { ++ ans ; } } return ans ; } private boolean check ( String token ) { int n = token . length (); if ( n == 0 ) { return false ; } boolean hyphen = false ; for ( int i = 0 ; i < n ; ++ i ) { char c = token . charAt ( i ); if ( Character . isDigit ( c ) || ( i < n - 1 && ( c == '!' || c == '.' || c == ',' ))) { return false ; } if ( c == '-' ) { if ( hyphen || i == 0 || i == n - 1 || ! Character . isLetter ( token . charAt ( i - 1 )) || ! Character . isLetter ( token . charAt ( i + 1 ))) { return false ; } hyphen = true ; } } return true ; } }
```

### CPP

```cpp
class Solution { public: int countValidWords ( string sentence ) { auto check = []( const string & s ) -> int { bool st = false ; for ( int i = 0 ; i < s . length (); ++ i ) { if ( isdigit ( s [ i ])) { return 0 ; } if (( s [ i ] == '!' || s [ i ] == '.' || s [ i ] == ',' ) && i < s . length () - 1 ) { return 0 ; } if ( s [ i ] == '-' ) { if ( st || i == 0 || i == s . length () - 1 ) { return 0 ; } if ( ! isalpha ( s [ i - 1 ]) || ! isalpha ( s [ i + 1 ])) { return 0 ; } st = true ; } } return 1 ; }; int ans = 0 ; stringstream ss ( sentence ); string s ; while ( ss >> s ) { ans += check ( s ); } return ans ; } };
```

### Python

```python
class Solution : def countValidWords ( self , sentence : str ) -> int : def check ( token ): hyphen = False for i , c in enumerate ( token ): if c . isdigit () or ( c in '!.,' and i < len ( token ) - 1 ): return False if c == '-' : if ( hyphen or i == 0 or i == len ( token ) - 1 or not token [ i - 1 ]. islower () or not token [ i + 1 ]. islower () ): return False hyphen = True return True return sum ( check ( token ) for token in sentence . split ())
```