| comments | difficulty | edit_url | rating | source | tags | |
|---|---|---|---|---|---|---|
true |
Easy |
1471 |
Weekly Contest 264 Q1 |
|
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.
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
For each character
- 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
class Solution:
def countValidWords(self, sentence: str) -> int:
def check(s: str) -> bool:
st = False
for i, c in enumerate(s):
if c.isdigit() or (c in "!.," and i < len(s) - 1):
return False
if c == "-":
if (
st
or i in (0, len(s) - 1)
or not s[i - 1].isalpha()
or not s[i + 1].isalpha()
):
return False
st = True
return True
return sum(check(s) for s in sentence.split())class Solution {
public int countValidWords(String sentence) {
int ans = 0;
for (String s : sentence.split(" ")) {
ans += check(s.toCharArray());
}
return ans;
}
private int check(char[] s) {
if (s.length == 0) {
return 0;
}
boolean st = false;
for (int i = 0; i < s.length; ++i) {
if (Character.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 (!Character.isAlphabetic(s[i - 1]) || !Character.isAlphabetic(s[i + 1])) {
return 0;
}
st = true;
}
}
return 1;
}
}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;
}
};func countValidWords(sentence string) (ans int) {
check := func(s string) int {
if len(s) == 0 {
return 0
}
st := false
for i, r := range s {
if unicode.IsDigit(r) {
return 0
}
if (r == '!' || r == '.' || r == ',') && i < len(s)-1 {
return 0
}
if r == '-' {
if st || i == 0 || i == len(s)-1 {
return 0
}
if !unicode.IsLetter(rune(s[i-1])) || !unicode.IsLetter(rune(s[i+1])) {
return 0
}
st = true
}
}
return 1
}
for _, s := range strings.Fields(sentence) {
ans += check(s)
}
return ans
}function countValidWords(sentence: string): number {
const check = (s: string): number => {
if (s.length === 0) {
return 0;
}
let st = false;
for (let i = 0; i < s.length; ++i) {
if (/\d/.test(s[i])) {
return 0;
}
if (['!', '.', ','].includes(s[i]) && i < s.length - 1) {
return 0;
}
if (s[i] === '-') {
if (st || [0, s.length - 1].includes(i)) {
return 0;
}
if (!/[a-zA-Z]/.test(s[i - 1]) || !/[a-zA-Z]/.test(s[i + 1])) {
return 0;
}
st = true;
}
}
return 1;
};
return sentence.split(/\s+/).reduce((acc, s) => acc + check(s), 0);
}