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:
'-'. If present, it must be surrounded by lowercase characters ("a-b" is valid, but "-ab" and "ab-" are not valid)."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 <= 1000sentence only contains lowercase English letters, digits, ' ', '-', '!', '.', and ','.1 token.In #2047 Number of Valid Words in a Sentence, the goal is to count how many tokens in a sentence follow specific validity rules. A common approach is to split the sentence by spaces to extract individual tokens and then validate each token according to the problem constraints.
A valid token can contain only lowercase letters, at most one - hyphen that must be surrounded by letters, and optionally one punctuation mark (!, ., ,) that must appear only at the end. Tokens containing digits or misplaced punctuation are invalid.
For each token, iterate through its characters and enforce these conditions while tracking the number of hyphens and punctuation positions. If the token satisfies all rules, increment the valid word counter. This character-by-character validation ensures correctness while keeping the logic straightforward.
The overall approach processes each character once, resulting in linear time complexity relative to the sentence length and constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Tokenization and rule-based validation | O(n) | O(1) |
Edignite Ngo
Use these hints if you're stuck. Try solving on your own first.
Iterate through the string to split it by spaces.
Count the number of characters of each type (letters, numbers, hyphens, and punctuations).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like this are common in coding interviews because they test string parsing and careful rule implementation. While the exact question may not always appear, similar validation or token-processing problems are frequently asked in FAANG-style interviews.
A valid word can only contain lowercase letters, at most one hyphen placed between letters, and optionally one punctuation mark (!, ., ,) only at the end. Digits are not allowed, and punctuation cannot appear in the middle of the token. Any token violating these rules is considered invalid.
No complex data structure is required for this problem. Simple string traversal with counters or flags for hyphens and punctuation is sufficient. Basic string operations and conditional checks handle all validation rules effectively.
The optimal approach is to split the sentence into tokens and validate each token using rule-based checks. By scanning each character once and enforcing constraints on hyphens, punctuation, and digits, we can determine validity efficiently. This results in linear time complexity relative to the sentence length.