Number of Valid Words in a Sentence

Difficulty: Easy | Acceptance: 31.10% | Paid: No Topics: String

A sentence consists of lowercase letters (‘a’ to ‘z’), digits (‘0’ to ‘9’), hyphens (’-’), punctuation marks (’!’, ’.’, and ’,’), and spaces (’ ’). Each sentence can be separated into one or more tokens separated by a single space.

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: “a-b.”, “cat”, “and”, “dance”, “a-b-c” Examples of invalid words: “rat-”, “a-b”, “a-b-c-”, “a-b-c.”, “a-”

Given a string sentence, return the number of valid words in sentence.

• Examples
• Constraints
• Iterative Validation
• Regular Expression
• State Machine

Examples

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 ','.
sentence does not have leading or trailing spaces.
All the words in sentence are separated by a single space.

Iterative Validation

Intuition For each word, iterate through characters while tracking hyphen count, punctuation position, and checking for invalid digits.

Steps

• Split the sentence by spaces to get individual words
• For each word, initialize counters for hyphens and punctuation
• Iterate through each character:
  • If digit found, word is invalid
  • If hyphen found, check if it’s surrounded by letters and count <= 1
  • If punctuation found, ensure it’s at the end and count <= 1
• Count all words that pass all validation rules

class Solution:
    def countValidWords(self, sentence: str) -> int:
        def is_valid(word):
            hyphen_count = 0
            punctuation_count = 0
            n = len(word)
            
            for i, ch in enumerate(word):
                if ch.isdigit():
                    return False
                elif ch == '-':
                    hyphen_count += 1
                    if hyphen_count > 1:
                        return False
                    if i == 0 or i == n - 1:
                        return False
                    if not word[i-1].isalpha() or not word[i+1].isalpha():
                        return False
                elif ch in '!,.':
                    punctuation_count += 1
                    if punctuation_count > 1:
                        return False
                    if i != n - 1:
                        return False
            return True
        
        words = sentence.split()
        return sum(1 for word in words if is_valid(word))

Complexity

• Time: O(n) where n is the length of the sentence
• Space: O(n) for storing the split words
• Notes: Simple and straightforward approach with clear logic

Regular Expression

Intuition Use regex pattern matching to validate each word against all rules in a single pattern.

Steps

• Split the sentence by spaces to get individual words
• Define a regex pattern that matches valid words:
  • ^[a-z]+ - starts with one or more letters
  • (-[a-z]+)? - optionally followed by hyphen and more letters
  • [!,.]?$ - optionally ends with a single punctuation
• Count words that match the pattern

import re

class Solution:
    def countValidWords(self, sentence: str) -> int:
        pattern = re.compile(r'^[a-z]+(-[a-z]+)?[!,.]?$')
        words = sentence.split()
        return sum(1 for word in words if pattern.match(word))

Complexity

• Time: O(n) where n is the length of the sentence
• Space: O(n) for storing the split words
• Notes: Concise code but regex may have overhead; pattern handles all rules elegantly

State Machine

Intuition Use a finite state machine to track the validation state as we process each character.

Steps

• Define states: START, LETTER, HYPHEN, PUNCTUATION, INVALID
• For each word, start in START state
• Transition between states based on character type:
  • Letter: can go to LETTER from START or LETTER or HYPHEN
  • Hyphen: can only go to HYPHEN from LETTER
  • Punctuation: can only go to PUNCTUATION from START or LETTER
  • Digit: go to INVALID
• Word is valid if ends in START, LETTER, or PUNCTUATION state

class Solution:
    def countValidWords(self, sentence: str) -> int:
        START, LETTER, HYPHEN, PUNCTUATION, INVALID = 0, 1, 2, 3, 4
        
        def is_valid(word):
            state = START
            hyphen_seen = False
            
            for i, ch in enumerate(word):
                if ch.isdigit():
                    return False
                elif ch.isalpha():
                    state = LETTER
                elif ch == '-':
                    if hyphen_seen or state != LETTER:
                        return False
                    hyphen_seen = True
                    state = HYPHEN
                elif ch in '!,.':
                    if i != len(word) - 1:
                        return False
                    state = PUNCTUATION
            
            return state != INVALID
        
        words = sentence.split()
        return sum(1 for word in words if is_valid(word))

Complexity

• Time: O(n) where n is the length of the sentence
• Space: O(n) for storing the split words
• Notes: Structured approach that clearly models validation rules as state transitions