Number of Valid Words in a Sentence
EasyPrompt
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 <= 1000sentenceonly contains lowercase English letters, digits,' ','-','!','.', and','.- There will be at least
1token.
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Split the
sentenceinto an array oftokensusing one or more spaces as the delimiter. - Initialize
validWordCount = 0. - For each
tokenin thetokensarray:- If the
tokenis not empty, call a helper functionisValid(token). - If
isValid(token)returnstrue, incrementvalidWordCount.
- If the
- 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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Define the regex pattern for a valid word:
^([a-z]+(-[a-z]+)?)?[!.,]?$. - Split the
sentenceinto an array oftokensusing spaces as delimiters. - Initialize
validWordCount = 0. - For each
tokenintokens:- If the
tokenis not empty and matches the regex pattern, incrementvalidWordCount.
- If the
- Return
validWordCount.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Initialize
validWordCount = 0and pointers/indicesstartandend. - 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
startpointer past the current token and any subsequent spaces. - Return
validWordCount.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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
startandendpointers) is slightly more complex than simply callingsplit().
Solutions
Solution
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 ; } }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 ; } };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 ())Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.