【Leetcode】3136. 有效单词

题目

LeetCode 3136. 有效单词

题目描述

有效单词需要满足以下几个条件：

1. 至少包含3个字符
2. 由数字0-9和英文大小写字母组成（不必包含所有这类字符）
3. 至少包含一个元音字母
4. 至少包含一个辅音字母

给你一个字符串word，如果word是一个有效单词，则返回true，否则返回false。

注意：

• ‘a’、‘e’、‘i’、‘o’、‘u’ 及其大写形式都属于元音字母
• 英文中的辅音字母是指那些除元音字母之外的字母

思路

这道题可以用两种方法来解决：

方法一：遍历计数法

1. 首先检查字符串长度是否至少为3
2. 遍历字符串的每个字符：
   • 如果遇到非法字符（@、#、$），直接返回false
   • 统计元音字母和辅音字母的数量
3. 最后检查是否至少有1个元音字母和1个辅音字母

方法二：正则表达式法

使用正则表达式一次性检查所有条件：

• (?=.*[aeiouAEIOU]) - 先行断言：至少包含一个元音字母
• (?=.*[bcdfghjklmnpqrstvwxyzBCDFGHJKLMNPQRSTVWXYZ]) - 先行断言：至少包含一个辅音字母
• [a-zA-Z0-9]{3,} - 只包含字母和数字，且长度至少为3

代码

C++

方法一：遍历计数法

class Solution {
public:
    bool isValid(string word) {
        // 检查长度
        if (word.length() < 3) {
            return false;
        }
        
        bool hasVowel = false;
        bool hasConsonant = false;
        string vowels = "aeiouAEIOU";
        
        for (char c : word) {
            // 检查是否为非法字符
            if (c == '@' || c == '#' || c == '$') {
                return false;
            }
            
            // 检查是否为元音
            if (vowels.find(c) != string::npos) {
                hasVowel = true;
            }
            // 检查是否为辅音（字母但不是元音）
            else if (isalpha(c)) {
                hasConsonant = true;
            }
        }
        
        return hasVowel && hasConsonant;
    }
};

方法二：正则表达式法

#include <regex>

class Solution {
public:
    bool isValid(string word) {
        // 使用正则表达式一次性检查所有条件
        regex pattern("^(?=.*[aeiouAEIOU])(?=.*[bcdfghjklmnpqrstvwxyzBCDFGHJKLMNPQRSTVWXYZ])[a-zA-Z0-9]{3,}$");
        return regex_match(word, pattern);
    }
};

Java

方法一：遍历计数法

class Solution {
    public boolean isValid(String word) {
        // 检查长度
        if (word.length() < 3) {
            return false;
        }
        
        boolean hasVowel = false;
        boolean hasConsonant = false;
        String vowels = "aeiouAEIOU";
        
        for (char c : word.toCharArray()) {
            // 检查非法字符
            if (c == '@' || c == '#' || c == '$') {
                return false;
            }
            
            // 检查元音
            if (vowels.indexOf(c) != -1) {
                hasVowel = true;
            }
            // 检查辅音
            else if (Character.isLetter(c)) {
                hasConsonant = true;
            }
        }
        
        return hasVowel && hasConsonant;
    }
}

方法二：正则表达式法

class Solution {
    public boolean isValid(String word) {
        // 使用正则表达式一次性检查所有条件
        String regex = "^(?=.*[aeiouAEIOU])(?=.*[bcdfghjklmnpqrstvwxyzBCDFGHJKLMNPQRSTVWXYZ])[a-zA-Z0-9]{3,}$";
        return word.matches(regex);
    }
}

Python

方法一：遍历计数法

class Solution:
    def isValid(self, word: str) -> bool:
        # 检查长度
        if len(word) < 3:
            return False
        
        has_vowel = False
        has_consonant = False
        vowels = "aeiouAEIOU"
        
        for char in word:
            # 检查非法字符
            if char in "@#$":
                return False
            
            # 检查元音
            if char in vowels:
                has_vowel = True
            # 检查辅音
            elif char.isalpha():
                has_consonant = True
        
        return has_vowel and has_consonant

方法二：正则表达式法

import re

class Solution:
    def isValid(self, word: str) -> bool:
        # 使用正则表达式一次性检查所有条件
        pattern = r"^(?=.*[aeiouAEIOU])(?=.*[bcdfghjklmnpqrstvwxyzBCDFGHJKLMNPQRSTVWXYZ])[a-zA-Z0-9]{3,}$"
        return bool(re.match(pattern, word))

复杂度分析

时间复杂度

• 方法一（遍历计数法）: O(n)，其中n是字符串的长度。需要遍历字符串一次。
• 方法二（正则表达式法）: O(n)，正则表达式匹配的时间复杂度也是O(n)。

空间复杂度

• 方法一: O(1)，只使用了常数个变量来存储状态。
• 方法二: O(1)，正则表达式编译后占用常数空间。

结果

以上两种方法都能正确解决问题，在LeetCode上的表现：

• 遍历计数法：更直观，易于理解和调试
• 正则表达式法：代码更简洁，但需要掌握正则表达式语法

总结

这道题考查的是字符串处理和条件判断。两种解法各有优势：

1. 遍历计数法：逻辑清晰，容易理解，适合在面试中使用
2. 正则表达式法：代码简洁，但需要较好的正则表达式基础

建议在实际开发中根据团队的技术栈和维护性要求选择合适的方法。对于这类字符串验证问题，遍历法通常是更安全和可维护的选择。