2047. Number of Valid Words in a Sentence
Description
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 <= 1000
sentence
only contains lowercase English letters, digits,' '
,'-'
,'!'
,'.'
, and','
.- There will be at least
1
token.
Solutions
Solution 1: Simulation
First, we split the sentence into words by spaces, and then check each word to determine if it is a valid word.
For each word, we can use a boolean variable $\textit{st}$ to record whether a hyphen has already appeared, and then traverse each character in the word, judging according to the rules described in the problem.
For each character $s[i]$, we have the following cases:
- If $s[i]$ is a digit, then $s$ is not a valid word, and we return $\text{false}$ directly;
- If $s[i]$ is a punctuation mark ('!', '.', ','), and $i < \text{len}(s) - 1$, then $s$ is not a valid word, and we return $\text{false}$ directly;
- If $s[i]$ is a hyphen, then we need to check if the following conditions are met:
- The hyphen can only appear once;
- The hyphen cannot appear at the beginning or end of the word;
- Both sides of the hyphen must be letters;
- If $s[i]$ is a letter, then we do not need to do anything.
Finally, we count the number of valid words in the sentence.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the sentence.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
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 26 27 28 29 30 31 32 33 34 |
|
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 26 27 28 29 30 31 32 33 34 |
|