2047. 句子中的有效单词数

🟢   🔖  字符串  🔗 力扣 LeetCode

题目

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.

题目大意

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

解题思路

1. 分割句子：使用空格 split 将句子分割为单词或标点符号的数组。

2. 过滤条件：通过一系列正则表达式的条件，过滤出符合规则的单词或标点符号。

3. 过滤规则

   • 移除带数字或空字符串的项：

     • if (/\d/.test(s) || s === '') return false
     • 如果字符串中包含数字 \d 或是空字符串 ''，直接排除。

   • 只包含标点符号的项：

     • if (/^[!,.]$/.test(s)) return true
     • 如果字符串仅由 !、, 或 . 组成，保留。

   • 单词+可选标点符号的项：

     • if (/^\w+[!,.]?$/.test(s)) return true
     • 匹配：
       • 至少包含一个字母或数字的单词：\w+
       • 可选的标点符号 !, ,, .：[!,.]?

   • 单词-单词+可选标点符号的项：

     • if (/^\w+[-]?\w+[!,.]?$/.test(s)) return true
     • 匹配：
       • 单词部分：\w+
       • 可选连字符：[-]?
       • 第二个单词部分：\w+
       • 可选标点符号 !, ,, .：[!,.]?

   • 不符合上述条件的项：

     • return false

4. 返回结果： 过滤后，返回符合条件的字符串数量：

复杂度分析

• 时间复杂度：O(n + m * k)

  • 分割句子：O(n)，其中 n 是字符串的长度。
  • 过滤过程：假设分割后的数组长度为 m，每次正则匹配的复杂度为 O(k)（k 是每个字符串的长度）。
    • 总过滤复杂度为 O(m * k)。
  • 总体复杂度：O(n + m * k)。

• 空间复杂度：O(m)，存储分割后的数组。

代码

/**
 * @param {string} sentence
 * @return {number}
 */
var countValidWords = function (sentence) {
	let list = sentence.split(' ');
	let filtered = list.filter((s) => {
		if (/\d/.test(s) || s === '') return false;
		if (/^[!,.]$/.test(s)) return true;
		if (/^\w+[!,.]?$/.test(s)) return true;
		if (/^\w+[-]?\w+[!,.]?$/.test(s)) return true;
		return false;
	});

	return filtered.length;
};

相关题目

题号	标题	题解	标签	难度	力扣
2114	句子中的最多单词数	[✓]	数组 字符串	🟢	🀄️ 🔗