句子中的有效单词数

标签: 字符串

难度: Easy

句子仅由小写字母（'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

Submission

运行时间: 34 ms

内存: 16.2 MB

class Solution:
    def countValidWords(self, sentence: str) -> int:
        s = list(sentence.split())
        ans = len(s)
        for i in range(len(s)):
            flag = 0
            for j in range(len(s[i])):
                #出现数字
                if 48<=ord(s[i][j])<=57:
                    ans -= 1
                    break
                #如果是连字符：
                if s[i][j] == '-':
                    if flag == 1:
                        ans -= 1
                        break
                    else:
                        if j == 0 or j == len(s[i])-1:
                            ans -= 1
                            break
                        else:
                            if 97<=ord(s[i][j-1])<=122 and 97<=ord(s[i][j+1])<=122:
                                ans += 0
                                flag = 1
                            else:
                                ans -= 1
                                break
                #如果是标点符号
                if s[i][j] =='!' or s[i][j] =='.' or s[i][j] ==',':
                    if j != len(s[i])-1:
                        ans -= 1
                        break
        return ans

Explain

解题思路主要是通过检查每一个token是否满足有效单词的定义。首先，使用split()方法将句子分割成token列表。然后，对每个token逐个进行检查，以判断其是否为有效单词。有效单词的条件包括：不包含数字，至多包含一个连字符（连字符必须位于两个小写字母之间），以及至多一个位于token末尾的标点符号。具体的检查过程是通过遍历每个token中的每个字符，并根据字符的类型（数字、连字符或标点符号）进行相应的检查。如果发现token不符合有效单词的标准，则从总数中减去一个计数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def countValidWords(self, sentence: str) -> int:
        s = list(sentence.split()) # 将句子分割成token列表
        ans = len(s) # 初始有效单词数量设为token数量
        for i in range(len(s)): # 遍历每个token
            flag = 0 # 用于标记是否已经遇到连字符
            for j in range(len(s[i])): # 遍历token中的每个字符
                # 检查是否含数字
                if 48<=ord(s[i][j])<=57:
                    ans -= 1 # 含数字，非有效单词
                    break
                # 检查连字符
                if s[i][j] == '-':
                    if flag == 1: # 已存在连字符，非有效单词
                        ans -= 1
                        break
                    else:
                        if j == 0 or j == len(s[i])-1: # 连字符在开头或结尾，非有效单词
                            ans -= 1
                            break
                        else:
                            if 97<=ord(s[i][j-1])<=122 and 97<=ord(s[i][j+1])<=122: # 连字符两侧都是小写字母
                                flag = 1 # 标记已遇到连字符
                            else:
                                ans -= 1 # 连字符两侧不都是小写字母，非有效单词
                                break
                # 检查标点符号
                if s[i][j] =='!' or s[i][j] =='.' or s[i][j] ==',':
                    if j != len(s[i])-1: # 标点不在末尾，非有效单词
                        ans -= 1
                        break
        return ans # 返回有效单词的数量

Explore

使用ASCII值范围来判断字符是否是数字提供了一种更为底层和通用的方法，这使得该逻辑在不同的编程环境中更容易理解和维护。此外，进行ASCII值范围比较可以在没有直接字符比较支持的环境中使用，增加代码的兼容性。然而，在大多数现代编程语言中，直接使用字符比较（如 '0' <= c <= '9'）通常更直观且易读。

是的，当前的逻辑在遇到第二个连字符后会立即减少`ans`的值，并终止当前token的检查。这确保了即使token中包含多个连字符，`ans`的值也只会因该token减少一次。因此，这个处理方式不会导致对同一个token的有效性判断多次减值。

是的，该逻辑被正确处理。代码中对连字符的位置进行了检查，如果连字符位于token的开头或结尾，则判断为无效单词。如果连字符位于其他位置，代码还会检查连字符两侧是否都是小写字母。因此，如果连字符在第二个位置或倒数第二个位置，且其一侧不是小写字母，该token会被正确地判断为无效单词。

是的，根据当前代码逻辑，如果一个token中有多个标点符号但只有最后一个位于末尾，则该token被视为有效单词。这是因为代码中的标点检查只关注标点是否出现在非末尾位置。如果出现非末尾的标点，会直接判断token为无效，而不会进一步检测是否还有其他标点。这可能是一个潜在的代码漏洞，应该加强对多个标点的检查。