2047-句子中的有效单词数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

句子仅由小写字母（'a' 到 'z'）、数字（'0' 到 '9'）、连字符（'-'）、标点符号（'!'、'.' 和
','）以及空格（' '）组成。每个句子可以根据空格分解成 一个或者多个 token ，这些 token 之间由一个或者多个空格 ' '
分隔。

如果一个 token 同时满足下述条件，则认为这个 token 是一个有效单词：

  • 仅由小写字母、连字符和/或标点（不含数字）组成。
  • 至多一个 连字符 '-' 。如果存在，连字符两侧应当都存在小写字母（"a-b" 是一个有效单词，但 "-ab" 和 "ab-" 不是有效单词）。
  • 至多一个 标点符号。如果存在，标点符号应当位于 token 的 末尾 。

这里给出几个有效单词的例子："a-b."、"afad"、"ba-c"、"a!" 和 "!" 。

给你一个字符串 sentence ，请你找出并返回 __sentence 中 有效单词的数目 。

示例 1：

**输入：** sentence = " _ **cat**_ _**and**_  _**dog**_ "
**输出：** 3
**解释：** 句子中的有效单词是 "cat"、"and" 和 "dog"

示例 2：

**输入：** sentence = "!this  1-s b8d!"
**输出：** 0
**解释：** 句子中没有有效单词
"!this" 不是有效单词，因为它以一个标点开头
"1-s" 和 "b8d" 也不是有效单词，因为它们都包含数字

示例 3：

**输入：** sentence = " _ **alice**_ _**and**_  _**bob**_ _**are**_ _**playing**_ stone-game10"
**输出：** 5
**解释：** 句子中的有效单词是 "alice"、"and"、"bob"、"are" 和 "playing"
"stone-game10" 不是有效单词，因为它含有数字

提示：

  • 1 <= sentence.length <= 1000
  • sentence 由小写英文字母、数字（0-9）、以及字符（' '、'-'、'!'、'.' 和 ','）组成
  • 句子中至少有 1 个 token

方法一：遍历

思路与算法

首先将句子按空格分隔成单词，然后判断单词是否有效。由题意知，单词不有效的条件为以下其中之一：

  • 单词中包含数字；

  • 单词中包含两个以上连字符；

  • 连字符在单词头部或者单词末尾；

  • 连字符的左/右边字符不是小写字母；

  • 单词中的标点符号不在单词的末尾。

记录有效的单词的个数，即为答案。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def countValidWords(self, sentence: str) -> int:
        def valid(s: str) -> bool:
            hasHyphens = False
            for i, ch in enumerate(s):
                if ch.isdigit() or ch in "!.," and i < len(s) - 1:
                    return False
                if ch == '-':
                    if hasHyphens or i == 0 or i == len(s) - 1 or not s[i - 1].islower() or not s[i + 1].islower():
                        return False
                    hasHyphens = True
            return True

        return sum(valid(s) for s in sentence.split())
[sol1-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
42
43
44
45
46
class Solution {
public:
    int countValidWords(string sentence) {
        int n = sentence.length();
        int l = 0, r = 0;
        int ret = 0;
        string_view slice(sentence);
        while (true) {
            while (l < n && sentence[l] == ' ') {
                l++;
            }
            if (l >= n) {
                break;
            }
            r = l + 1;
            while (r < n && sentence[r] != ' ') {
                r++;
            }
            if (isValid(slice.substr(l, r - l))) { // 判断根据空格分解出来的 token 是否有效
                ret++;
            }
            l = r + 1;
        }
        return ret;
    }

    bool isValid(const string_view &word) {
        int n = word.length();
        bool has_hyphens = false;
        for (int i = 0; i < n; i++) {
            if (word[i] >= '0' && word[i] <= '9') {
                return false;
            } else if (word[i] == '-') {
                if (has_hyphens == true || i == 0 || i == n - 1 || !islower(word[i - 1]) || !islower(word[i + 1])) {
                    return false;
                }
                has_hyphens = true;
            } else if (word[i] == '!' || word[i] == '.' || word[i] == ',') {
                if (i != n - 1) {
                    return false;
                }
            }
        }
        return true;
    }
};
[sol1-Java]
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
42
43
44
class Solution {
    public int countValidWords(String sentence) {
        int n = sentence.length();
        int l = 0, r = 0;
        int ret = 0;
        while (true) {
            while (l < n && sentence.charAt(l) == ' ') {
                l++;
            }
            if (l >= n) {
                break;
            }
            r = l + 1;
            while (r < n && sentence.charAt(r) != ' ') {
                r++;
            }
            if (isValid(sentence.substring(l, r))) { // 判断根据空格分解出来的 token 是否有效
                ret++;
            }
            l = r + 1;
        }
        return ret;
    }

    public boolean isValid(String word) {
        int n = word.length();
        boolean hasHyphens = false;
        for (int i = 0; i < n; i++) {
            if (Character.isDigit(word.charAt(i))) {
                return false;
            } else if (word.charAt(i) == '-') {
                if (hasHyphens == true || i == 0 || i == n - 1 || !Character.isLetter(word.charAt(i - 1)) || !Character.isLetter(word.charAt(i + 1))) {
                    return false;
                }
                hasHyphens = true;
            } else if (word.charAt(i) == '!' || word.charAt(i) == '.' || word.charAt(i) == ',') {
                if (i != n - 1) {
                    return false;
                }
            }
        }
        return true;
    }
}
[sol1-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
42
43
44
public class Solution {
    public int CountValidWords(string sentence) {
        int n = sentence.Length;
        int l = 0, r = 0;
        int ret = 0;
        while (true) {
            while (l < n && sentence[l] == ' ') {
                l++;
            }
            if (l >= n) {
                break;
            }
            r = l + 1;
            while (r < n && sentence[r] != ' ') {
                r++;
            }
            if (isValid(sentence.Substring(l, r - l))) { // 判断根据空格分解出来的 token 是否有效
                ret++;
            }
            l = r + 1;
        }
        return ret;
    }

    public bool isValid(string word) {
        int n = word.Length;
        bool hasHyphens = false;
        for (int i = 0; i < n; i++) {
            if (char.IsDigit(word[i])) {
                return false;
            } else if (word[i] == '-') {
                if (hasHyphens == true || i == 0 || i == n - 1 || !char.IsLetter(word[i - 1]) || !char.IsLetter(word[i + 1])) {
                    return false;
                }
                hasHyphens = true;
            } else if (word[i] == '!' || word[i] == '.' || word[i] == ',') {
                if (i != n - 1) {
                    return false;
                }
            }
        }
        return true;
    }
}
[sol1-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
bool isValid(char *word, int n) {
    int has_hyphens = 0;
    for (int i = 0; i < n; i++) {
        if (word[i] >= '0' && word[i] <= '9') {
            return false;
        } else if (word[i] == '-') {
            if (has_hyphens == 1 || i == 0 || i == n - 1 || !islower(word[i - 1]) || !islower(word[i + 1])) {
                return false;
            }
            has_hyphens = 1;
        } else if (word[i] == '!' || word[i] == '.' || word[i] == ',') {
            if (i != n - 1) {
                return false;
            }
        }
    }
    return true;
}

int countValidWords(char * sentence){
    int n = strlen(sentence);
    int l = 0, r = 0;
    int ret = 0;
    while (true) {
        while (l < n && sentence[l] == ' ') {
            l++;
        }
        if (l >= n) {
            break;
        }
        r = l + 1;
        while (r < n && sentence[r] != ' ') {
            r++;
        }
        if (isValid(sentence + l, r - l)) { // 判断根据空格分解出来的 token 是否有效
            ret++;
        }
        l = r + 1;
    }
    return ret;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func valid(s string) bool {
    hasHyphens := false
    for i, ch := range s {
        if unicode.IsDigit(ch) || strings.ContainsRune("!.,", ch) && i < len(s)-1 {
            return false
        }
        if ch == '-' {
            if hasHyphens || i == 0 || i == len(s)-1 || !unicode.IsLower(rune(s[i-1])) || !unicode.IsLower(rune(s[i+1])) {
                return false
            }
            hasHyphens = true
        }
    }
    return true
}

func countValidWords(sentence string) (ans int) {
    for _, s := range strings.Fields(sentence) { // 按照空格分割
        if valid(s) {
            ans++
        }
    }
    return
}
[sol1-JavaScript]
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
42
43
44
45
46
47
48
49
var countValidWords = function(sentence) {
    const n = sentence.length;
    let l = 0, r = 0;
    let ret = 0;
    while (true) {
        while (l < n && sentence[l] === ' ') {
            l++;
        }
        if (l >= n) {
            break;
        }
        r = l + 1;
        while (r < n && sentence[r] != ' ') {
            r++;
        }
        if (isValid(sentence.slice(l, r))) { // 判断根据空格分解出来的 token 是否有效
            ret++;
        }
        l = r + 1;
    }
    return ret;
};

const isValid = (word) => {
    const n = word.length;
    let hasHyphens = false;
    for (let i = 0; i < n; i++) {
        if (word[i] >= '0' && word[i] <= '9') {
            return false;
        } else if (word[i] === '-') {
            if (hasHyphens === true || i === 0 || i === n - 1 || !isLetter(word[i - 1]) || !isLetter(word[i + 1])) {
                return false;
            }
            hasHyphens = true;
        } else if (word[i] === '!' || word[i] === '.' || word[i] === ',') {
            if (i !== n - 1) {
                return false;
            }
        }
    }
    return true;
}

const isLetter = (ch) => {
    if (ch >= 'a' && ch <= 'z' || ch >= 'A' && ch <= 'Z') {
        return true;
    }
    return false;
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是句子的长度。切分整个句子，并处理单词需要 O(n)。

  • 空间复杂度：O(1)。只需要常数空间保存变量。

 Comments
On this page
2047-句子中的有效单词数