Leetcode 2047: Number of Valid Words in a Sentence
A sentence consists of lowercase letters (‘a’ to ‘z’), digits (‘0’ to ‘9’), hyphens (’-’), punctuation marks (’!’, ‘.’, and ‘,’), and spaces (’ ‘) only. A token is any sequence of characters separated by spaces. A token is considered a valid word if all the following conditions are met:
- It does not contain any digits.
- It contains at most one hyphen (’-’), and if present, the hyphen must be surrounded by lowercase letters.
- It contains at most one punctuation mark, and if present, the punctuation mark must be at the end of the token.
Given a sentence, count the number of tokens that are valid words.
Problem
Approach
Steps
Complexity
Input: A string `sentence` consisting of lowercase English letters, digits, spaces, hyphens, and punctuation marks.
Example: Input: sentence = "hello world! test-case 1234, valid-word."
Constraints:
• 1 <= sentence.length <= 1000
• sentence contains at least one token.
• Sentence characters are limited to 'a'-'z', '0'-'9', '-', '!', '.', ',', and ' '.
Output: An integer representing the count of valid words in the sentence.
Example: Output: 2
Constraints:
• The output is always a non-negative integer.
Goal: Determine the number of valid words in the given sentence.
Steps:
• Split the sentence into tokens based on spaces.
• For each token, check if it satisfies the conditions for being a valid word.
• Count the tokens that are valid words.
Goal: Ensure all conditions for valid words are met during processing.
Steps:
• No digits are allowed in a valid word.
• At most one hyphen is allowed, and it must be surrounded by letters.
• At most one punctuation mark is allowed, and it must appear at the end of the word.
Assumptions:
• The input sentence always contains at least one token.
• Characters are limited to the defined set of letters, digits, and special characters.
• Input: Input: sentence = "word1 -a invalid! valid-word."
• Explanation: The valid words are "valid-word.". Other tokens fail due to digits, improper hyphen usage, or invalid punctuation placement. Output: 1.
• Input: Input: sentence = "a-b test valid! example."
• Explanation: The valid words are "a-b", "test", "valid!", and "example.". Output: 4.
Approach: Use a helper function to validate tokens according to the rules and iterate through the tokens of the sentence to count valid words.
Observations:
• A token is valid if it adheres to strict rules regarding digits, hyphens, and punctuation marks.
• Each token can be evaluated independently of others.
• The solution can efficiently process the sentence by splitting it into tokens and checking each token's validity using a helper function.
Steps:
• Split the input string into tokens using space as a delimiter.
• Define a helper function to validate a token according to the rules.
• Iterate through the tokens, validate each using the helper function, and count valid ones.
Empty Inputs:
• No empty input cases as the sentence is guaranteed to have at least one token.
Large Inputs:
• Sentences with maximum length (1000 characters).
Special Values:
• Tokens with only special characters like '---' or '...'.
• Tokens with mixed valid and invalid combinations like 'a--b' or 'a,b.'
Constraints:
• Ensure proper handling of edge cases like multiple spaces or trailing/leading spaces.
class Solution {
bool valid(string &s) {
int hyphen = 0, N = s.size();
for (int i = 0; i < N; ++i) {
if (isdigit(s[i])) return false; // no digit
if (isalpha(s[i])) continue; // skip letters
if (s[i] == '-') {
if (++hyphen > 1) return false; // at most one hyphen allowed
if (i - 1 < 0 || !isalpha(s[i - 1]) || i + 1 >= N || !isalpha(s[i + 1])) return false; // hyphen must be surrounded by letters
} else if (i != N - 1) return false; // punctuation, if any, must be the last character of token
}
return true;
}
public:
int countValidWords(string s) {
string w;
istringstream ss(s);
int ans = 0;
while (ss >> w) ans += valid(w);
return ans;
}
1 : Class Definition
class Solution {
This defines the `Solution` class, which contains the method `countValidWords` to solve the problem of counting valid words in a string.
2 : Helper Function Declaration
bool valid(string &s) {
This declares the `valid` helper function that checks if a given string `s` is a valid word.
3 : Variable Initialization
int hyphen = 0, N = s.size();
Initializes `hyphen` to count the number of hyphens and `N` to store the size of the string `s`.
4 : Loop Start
for (int i = 0; i < N; ++i) {
This loop iterates through each character of the string `s`.
5 : Digit Check
if (isdigit(s[i])) return false; // no digit
Checks if the current character is a digit. If so, returns `false` because digits are not allowed in valid words.
6 : Alpha Check
if (isalpha(s[i])) continue; // skip letters
If the character is a letter, it is valid, so the loop continues to the next character.
7 : Hyphen Check
if (s[i] == '-') {
Checks if the current character is a hyphen.
8 : Hyphen Count Check
if (++hyphen > 1) return false; // at most one hyphen allowed
If there is more than one hyphen in the word, returns `false` since only one hyphen is allowed.
9 : Hyphen Surrounding Check
if (i - 1 < 0 || !isalpha(s[i - 1]) || i + 1 >= N || !isalpha(s[i + 1])) return false; // hyphen must be surrounded by letters
Checks if the hyphen is properly surrounded by letters (both before and after). If not, returns `false`.
10 : Punctuation Check
} else if (i != N - 1) return false; // punctuation, if any, must be the last character of token
If the character is not a letter or hyphen and it is not the last character, returns `false` because punctuation should only appear at the end of the word.
11 : Return True
return true;
Returns `true` if the string `s` passed all validity checks, indicating it is a valid word.
12 : Public Section
public:
Marks the beginning of the public section of the class where the main solution method resides.
13 : Main Function Declaration
int countValidWords(string s) {
This is the declaration of the `countValidWords` function that counts the valid words in the given string `s`.
14 : String Initialization
string w;
Initializes the string `w`, which will be used to store individual words as the string `s` is processed.
15 : Stream Initialization
istringstream ss(s);
Initializes an input string stream `ss` to process the input string `s` word by word.
16 : Result Initialization
int ans = 0;
Initializes the integer `ans` to store the count of valid words.
17 : Loop Through Words
while (ss >> w) ans += valid(w);
This loop extracts words from the string stream `ss` and adds to `ans` the number of valid words using the `valid` function.
18 : Return Result
return ans;
Returns the total count of valid words.
Best Case: O(n), where n is the number of characters in the sentence.
Average Case: O(n), where n is the number of characters in the sentence.
Worst Case: O(n), where n is the number of characters in the sentence.
Description: Each token is processed in linear time relative to its length, and all tokens are processed sequentially.
Best Case: O(1) if token processing is done in place.
Worst Case: O(n) for storing tokens.
Description: Space is used for splitting the sentence into tokens and temporary storage during validation.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus