Easy

题目描述

句子仅由小写字母（‘a’ 到 ‘z’）、数字（‘0’ 到 ‘9’）、连字符（’-’）、标点符号（’!’、’.’ 和 ‘,’）以及空格（’ ‘）组成。每个句子可以分解成一个或多个由一个或多个空格分隔的标记。

如果一个标记满足下面三个条件，那么它是一个有效单词：

  • 仅含有小写字母、连字符和/或标点符号（没有数字）。
  • 至多一个 连字符 ‘-’。如果存在，连字符两侧应当有小写字母（“a-b” 是有效的，但是 “-ab” 和 “ab-” 不是有效的）。
  • 至多一个 标点符号。如果存在，标点符号应当在标记的 末尾（“ab,"、“cd!” 和 “.” 是有效的，但是 “a!b” 和 “c.,” 不是有效的）。

有效单词的例子包括 “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 仅由小写英文字母、数字、' '、'-'、'!'、'.' 和 ',' 组成
  • 至少有 1 个标记

解题思路

这道题要求我们判断句子中有效单词的数量。解题思路如下：

核心思路：

  1. 首先按空格分割句子，得到各个标记
  2. 对每个标记进行有效性检查，需要同时满足三个条件

有效单词的检查规则：

  • 字符类型检查：只能包含小写字母、连字符、标点符号，不能有数字
  • 连字符检查：至多一个连字符，且必须被小写字母包围（不能在开头或结尾）
  • 标点符号检查：至多一个标点符号，且必须在末尾

实现细节： 我们可以遍历每个标记的字符，同时统计连字符和标点符号的数量，并检查它们的位置是否合法。对于连字符，需要确保其前后都是小写字母；对于标点符号，需要确保它只出现在末尾。

这是一道典型的字符串模拟题，关键在于仔细处理各种边界情况和约束条件。时间复杂度主要取决于字符串的长度。

代码实现

class Solution {
public:
    int countValidWords(string sentence) {
        vector<string> tokens;
        string token;
        
        // 分割字符串
        for (char c : sentence) {
            if (c == ' ') {
                if (!token.empty()) {
                    tokens.push_back(token);
                    token.clear();
                }
            } else {
                token += c;
            }
        }
        if (!token.empty()) {
            tokens.push_back(token);
        }
        
        int count = 0;
        for (const string& word : tokens) {
            if (isValidWord(word)) {
                count++;
            }
        }
        return count;
    }
    
private:
    bool isValidWord(const string& word) {
        int hyphenCount = 0;
        int punctuationCount = 0;
        
        for (int i = 0; i < word.length(); i++) {
            char c = word[i];
            
            if (isdigit(c)) {
                return false; // 包含数字
            }
            
            if (c == '-') {
                hyphenCount++;
                if (hyphenCount > 1) return false; // 超过一个连字符
                if (i == 0 || i == word.length() - 1) return false; // 连字符在开头或末尾
                if (!islower(word[i-1]) || !islower(word[i+1])) return false; // 连字符两侧不是小写字母
            }
            
            if (c == '!' || c == '.' || c == ',') {
                punctuationCount++;
                if (punctuationCount > 1) return false; // 超过一个标点符号
                if (i != word.length() - 1) return false; // 标点符号不在末尾
            }
        }
        
        return true;
    }
};

class Solution:
    def countValidWords(self, sentence: str) -> int:
        tokens = sentence.split()
        count = 0
        
        for word in tokens:
            if self.isValidWord(word):
                count += 1
                
        return count
    
    def isValidWord(self, word: str) -> bool:
        hyphen_count = 0
        punctuation_count = 0
        
        for i, c in enumerate(word):
            if c.isdigit():
                return False  # 包含数字
            
            if c == '-':
                hyphen_count += 1
                if hyphen_count > 1:
                    return False  # 超过一个连字符
                if i == 0 or i == len(word) - 1:
                    return False  # 连字符在开头或末尾
                if not word[i-1].islower() or not word[i+1].islower():
                    return False  # 连字符两侧不是小写字母
            
            if c in '!.,':
                punctuation_count += 1
                if punctuation_count > 1:
                    return False  # 超过一个标点符号
                if i != len(word) - 1:
                    return False  # 标点符号不在末尾
        
        return True

public class Solution {
    public int CountValidWords(string sentence) {
        string[] tokens = sentence.Split(' ', StringSplitOptions.RemoveEmptyEntries);
        int count = 0;
        
        foreach (string word in tokens) {
            if (IsValidWord(word)) {
                count++;
            }
        }
        
        return count;
    }
    
    private bool IsValidWord(string word) {
        int hyphenCount = 0;
        int punctuationCount = 0;
        
        for (int i = 0; i < word.Length; i++) {
            char c = word[i];
            
            if (char.IsDigit(c)) {
                return false; // 包含数字
            }
            
            if (c == '-') {
                hyphenCount++;
                if (hyphenCount > 1) return false; // 超过一个连字符
                if (i == 0 || i == word.Length - 1) return false; // 连字符在开头或末尾
                if (!char.IsLower(word[i-1]) || !char.IsLower(word[i+1])) return false; // 连字符两侧不是小写字母
            }
            
            if (c == '!' || c == '.' || c == ',') {
                punctuationCount++;
                if (punctuationCount > 1) return false; // 超过一个标点符号
                if (i != word.Length - 1) return false; // 标点符号不在末尾
            }
        }
        
        return true;
    }
}

var countValidWords = function(sentence) {
    const tokens = sentence.split(/\s+/).filter(token => token.length > 0);
    let count = 0;
    
    for (let token of tokens) {
        if (isValidWord(token)) {
            count++;
        }
    }
    
    return count;
};

function isValidWord(word) {
    let hyphenCount = 0;
    let punctuationCount = 0;
    
    for (let i = 0; i < word.length; i++) {
        const char = word[i];
        
        if (char >= '0' && char <= '9') {
            return false;
        }
        
        if (char === '-') {
            hyphenCount++;
            if (hyphenCount > 1) return false;
            if (i === 0 || i === word.length - 1) return false;
            if (!(word[i-1] >= 'a' && word[i-1] <= 'z') || !(word[i+1] >= 'a' && word[i+1] <= 'z')) {
                return false;
            }
        }
        
        if (char === '!' || char === '.' || char === ',') {
            punctuationCount++;
            if (punctuationCount > 1) return false;
            if (i !== word.length - 1) return false;
        }
    }
    
    return true;
}
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)n 为句子长度，需要遍历每个字符进行检查
空间复杂度O(k)k 为标记数量，用于存储分割后的单词

相关题目