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:
- It only contains lowercase letters, hyphens, and/or punctuation (no digits).
- There is at most one hyphen
'-'. If present, it should 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 should be at the end of the token.
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.
Example 4:
Input: sentence = "he bought 2 pencils, 3 erasers, and 1 pencil-sharpener." Output: 6 Explanation: The valid words in the sentence are "he", "bought", "pencils,", "erasers,", "and", and "pencil-sharpener.".
Constraints:
1 <= sentence.length <= 1000sentenceonly contains lowercase English letters, digits,' ','-','!','.', and','.- There will be at least
1token.
Solution 1: Brute Force
Time complexity: O(n)
Space complexity: O(1)
C++
|
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 35 36 37 38 39 40 41 |
// Author: Huahua class Solution { public: int countValidWords(string sentence) { stringstream ss(sentence); string word; int ans = 0; while (ss >> word) { bool valid = true; int hyphen = 0; int punctuation = 0; char p = ' '; for (char c : word) { if (c == '-') { if (++hyphen > 1 || !isalpha(p)) { valid = false; break; } } else if (c == '!' || c == '.' || c == ',') { if (++punctuation > 1 || p == '-') { valid = false; break; } } else if (isalpha(c)) { if (punctuation) { valid = false; break; } } else { valid = false; break; } p = c; } if (word.back() == '-') valid = false; if (valid) ++ans; } return ans; } }; |
Solution 2: Regex
Time complexity: O(n^2)?
Space complexity: O(1)
Python
|
1 2 3 4 5 6 7 8 |
# Author: Huahua class Solution: def countValidWords(self, sentence: str) -> int: ans = 0 for word in sentence.split(): if word.strip() and re.fullmatch('^([a-z]+(-?[a-z]+)?)?[\.,!]?$', word.strip()): ans += 1 return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment