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 _thenumber of valid words in _sentence.

Examples

Example 1

1
2
3

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

Example 2

1
2
3
4
5

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

1
2
3
4

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.

Solution

Method 1 – String Parsing and Validation

Intuition

We need to check each token in the sentence for the three validity rules. This can be done by iterating through each character and checking for digits, hyphen placement, and punctuation placement.

Approach

  1. Split the sentence into tokens by spaces.
  2. For each token, check:
    • No digits present.
    • At most one hyphen, and if present, it is surrounded by lowercase letters.
    • At most one punctuation mark, and if present, it is at the end.
  3. Count the number of valid tokens.
  4. Return the count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int countValidWords(string sentence) {
        istringstream iss(sentence);
        string token;
        int ans = 0;
        while (iss >> token) {
            bool valid = true;
            int hyphen = 0, punct = 0, n = token.size();
            for (int i = 0; i < n; ++i) {
                char c = token[i];
                if (isdigit(c)) { valid = false; break; }
                if (c == '-') {
                    hyphen++;
                    if (hyphen > 1 || i == 0 || i == n-1 || !islower(token[i-1]) || !islower(token[i+1])) { valid = false; break; }
                }
                if (c == '!' || c == '.' || c == ',') {
                    if (i != n-1 || ++punct > 1) { valid = false; break; }
                }
            }
            if (valid) ans++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import "strings"
func countValidWords(sentence string) int {
    tokens := strings.Fields(sentence)
    ans := 0
    for _, token := range tokens {
        valid, hyphen, punct := true, 0, 0
        n := len(token)
        for i := 0; i < n; i++ {
            c := token[i]
            if c >= '0' && c <= '9' { valid = false; break }
            if c == '-' {
                hyphen++
                if hyphen > 1 || i == 0 || i == n-1 || token[i-1] < 'a' || token[i-1] > 'z' || token[i+1] < 'a' || token[i+1] > 'z' { valid = false; break }
            }
            if c == '!' || c == '.' || c == ',' {
                if i != n-1 || punct++; punct > 1 { valid = false; break }
            }
        }
        if valid { ans++ }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int countValidWords(String sentence) {
        String[] tokens = sentence.trim().split("\\s+");
        int ans = 0;
        for (String token : tokens) {
            if (token.isEmpty()) continue;
            boolean valid = true;
            int hyphen = 0, punct = 0, n = token.length();
            for (int i = 0; i < n; i++) {
                char c = token.charAt(i);
                if (Character.isDigit(c)) { valid = false; break; }
                if (c == '-') {
                    hyphen++;
                    if (hyphen > 1 || i == 0 || i == n-1 || !Character.isLowerCase(token.charAt(i-1)) || !Character.isLowerCase(token.charAt(i+1))) { valid = false; break; }
                }
                if (c == '!' || c == '.' || c == ',') {
                    if (i != n-1 || ++punct > 1) { valid = false; break; }
                }
            }
            if (valid) ans++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun countValidWords(sentence: String): Int {
        val tokens = sentence.trim().split(Regex("\\s+")).filter { it.isNotEmpty() }
        var ans = 0
        for (token in tokens) {
            var valid = true
            var hyphen = 0; var punct = 0; val n = token.length
            for (i in 0 until n) {
                val c = token[i]
                if (c.isDigit()) { valid = false; break }
                if (c == '-') {
                    hyphen++
                    if (hyphen > 1 || i == 0 || i == n-1 || !token[i-1].isLowerCase() || !token[i+1].isLowerCase()) { valid = false; break }
                }
                if (c == '!' || c == '.' || c == ',') {
                    if (i != n-1 || ++punct > 1) { valid = false; break }
                }
            }
            if (valid) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def countValidWords(self, sentence: str) -> int:
        def valid(token: str) -> bool:
            hyphen = punct = 0
            n = len(token)
            for i, c in enumerate(token):
                if c.isdigit(): return False
                if c == '-':
                    hyphen += 1
                    if hyphen > 1 or i == 0 or i == n-1 or not token[i-1].islower() or not token[i+1].islower():
                        return False
                if c in '!.,':
                    if i != n-1 or punct+1 > 1:
                        return False
                    punct += 1
            return True
        return sum(valid(token) for token in sentence.strip().split())
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn count_valid_words(sentence: String) -> i32 {
        fn valid(token: &str) -> bool {
            let mut hyphen = 0;
            let mut punct = 0;
            let n = token.len();
            let chars: Vec<char> = token.chars().collect();
            for (i, &c) in chars.iter().enumerate() {
                if c.is_ascii_digit() { return false; }
                if c == '-' {
                    hyphen += 1;
                    if hyphen > 1 || i == 0 || i == n-1 || !chars[i-1].is_ascii_lowercase() || !chars[i+1].is_ascii_lowercase() { return false; }
                }
                if c == '!' || c == '.' || c == ',' {
                    if i != n-1 || punct+1 > 1 { return false; }
                    punct += 1;
                }
            }
            true
        }
        sentence.split_whitespace().filter(|t| valid(t)).count() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    countValidWords(sentence: string): number {
        function valid(token: string): boolean {
            let hyphen = 0, punct = 0, n = token.length
            for (let i = 0; i < n; i++) {
                const c = token[i]
                if (c >= '0' && c <= '9') return false
                if (c === '-') {
                    hyphen++
                    if (hyphen > 1 || i === 0 || i === n-1 || token[i-1] < 'a' || token[i-1] > 'z' || token[i+1] < 'a' || token[i+1] > 'z') return false
                }
                if (c === '!' || c === '.' || c === ',') {
                    if (i !== n-1 || punct+1 > 1) return false
                    punct++
                }
            }
            return true
        }
        return sentence.trim().split(/\s+/).filter(valid).length
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the sentence.
  • 🧺 Space complexity: O(1), ignoring the output array.