966. 元音拼写检查器

Medium

题目描述

给定一个单词列表，我们需要实现一个拼写检查器，将查询单词转换为正确的单词。

对于给定的查询单词，拼写检查器处理两类拼写错误：

大小写错误：如果查询单词与单词列表中的某个单词匹配（忽略大小写），则返回单词列表中对应单词的原始大小写形式。

示例：wordlist = [“yellow”]，query = “YellOw”：正确答案 = “yellow”
示例：wordlist = [“Yellow”]，query = “yellow”：正确答案 = “Yellow”
示例：wordlist = [“yellow”]，query = “yellow”：正确答案 = “yellow”

元音错误：如果将查询单词的元音字母（‘a’, ’e’, ‘i’, ‘o’, ‘u’）替换为任意元音字母后，能与单词列表中的某个单词匹配（忽略大小写），则返回单词列表中对应单词的原始大小写形式。

示例：wordlist = [“YellOw”]，query = “yollow”：正确答案 = “YellOw”
示例：wordlist = [“YellOw”]，query = “yeellow”：正确答案 = “"（无匹配）
示例：wordlist = [“YellOw”]，query = “yllw”：正确答案 = “"（无匹配）

此外，拼写检查器按以下优先级规则运行：

当查询完全匹配单词列表中的单词（区分大小写）时，返回相同的单词。
当查询在大小写上匹配单词时，返回单词列表中第一个这样的匹配。
当查询在元音错误上匹配单词时，返回单词列表中第一个这样的匹配。
如果查询在单词列表中没有匹配，返回空字符串。

给定一些查询，返回一个单词列表 answer，其中 answer[i] 是 query = queries[i] 的正确单词。

示例 1：

输入：wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
输出：["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

示例 2：

输入：wordlist = ["yellow"], queries = ["YellOw"]
输出：["yellow"]

约束：

1 <= wordlist.length, queries.length <= 5000
1 <= wordlist[i].length, queries[i].length <= 7
wordlist[i] 和 queries[i] 仅由英文字母组成

解题思路

这是一个典型的哈希表应用题目，需要按照三个优先级进行匹配。

核心思路：

精确匹配：使用哈希集合存储所有原始单词，直接查找
大小写匹配：使用哈希表，键为小写单词，值为首次出现的原始单词
元音匹配：使用哈希表，键为将元音替换为统一字符（如’*’）后的小写单词，值为首次出现的原始单词

算法步骤：

预处理单词列表，构建三个哈希表：
- exact：存储所有原始单词
- lowercase：键为小写单词，值为第一个匹配的原始单词
- vowel_pattern：键为元音模式（元音替换为’*’），值为第一个匹配的原始单词
对每个查询单词，按优先级顺序查找：
- 先检查精确匹配
- 再检查大小写匹配
- 最后检查元音模式匹配
- 都不匹配则返回空字符串

时间复杂度优化： 通过预处理避免重复计算，每次查询只需O(1)时间完成匹配。

**推荐解法：**使用三个哈希表分别处理三种匹配规则，代码清晰且效率高。

代码实现

class Solution {
public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        unordered_set<string> exact;
        unordered_map<string, string> lowercase;
        unordered_map<string, string> vowel_pattern;
        
        auto toLower = [](string s) {
            for (char& c : s) c = tolower(c);
            return s;
        };
        
        auto getVowelPattern = [](string s) {
            for (char& c : s) {
                c = tolower(c);
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                    c = '*';
                }
            }
            return s;
        };
        
        for (const string& word : wordlist) {
            exact.insert(word);
            
            string lower = toLower(word);
            if (lowercase.find(lower) == lowercase.end()) {
                lowercase[lower] = word;
            }
            
            string pattern = getVowelPattern(word);
            if (vowel_pattern.find(pattern) == vowel_pattern.end()) {
                vowel_pattern[pattern] = word;
            }
        }
        
        vector<string> result;
        for (const string& query : queries) {
            if (exact.count(query)) {
                result.push_back(query);
            } else if (lowercase.count(toLower(query))) {
                result.push_back(lowercase[toLower(query)]);
            } else if (vowel_pattern.count(getVowelPattern(query))) {
                result.push_back(vowel_pattern[getVowelPattern(query)]);
            } else {
                result.push_back("");
            }
        }
        
        return result;
    }
};

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def get_vowel_pattern(s):
            return ''.join('*' if c.lower() in 'aeiou' else c.lower() for c in s)
        
        exact = set(wordlist)
        lowercase = {}
        vowel_pattern = {}
        
        for word in wordlist:
            lower = word.lower()
            if lower not in lowercase:
                lowercase[lower] = word
            
            pattern = get_vowel_pattern(word)
            if pattern not in vowel_pattern:
                vowel_pattern[pattern] = word
        
        result = []
        for query in queries:
            if query in exact:
                result.append(query)
            elif query.lower() in lowercase:
                result.append(lowercase[query.lower()])
            elif get_vowel_pattern(query) in vowel_pattern:
                result.append(vowel_pattern[get_vowel_pattern(query)])
            else:
                result.append("")
        
        return result

public class Solution {
    public string[] Spellchecker(string[] wordlist, string[] queries) {
        var exact = new HashSet<string>(wordlist);
        var lowercase = new Dictionary<string, string>();
        var vowelPattern = new Dictionary<string, string>();
        
        string GetVowelPattern(string s) {
            var chars = s.ToLower().ToCharArray();
            for (int i = 0; i < chars.Length; i++) {
                if ("aeiou".Contains(chars[i])) {
                    chars[i] = '*';
                }
            }
            return new string(chars);
        }
        
        foreach (string word in wordlist) {
            string lower = word.ToLower();
            if (!lowercase.ContainsKey(lower)) {
                lowercase[lower] = word;
            }
            
            string pattern = GetVowelPattern(word);
            if (!vowelPattern.ContainsKey(pattern)) {
                vowelPattern[pattern] = word;
            }
        }
        
        var result = new string[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            string query = queries[i];
            if (exact.Contains(query)) {
                result[i] = query;
            } else if (lowercase.ContainsKey(query.ToLower())) {
                result[i] = lowercase[query.ToLower()];
            } else if (vowelPattern.ContainsKey(GetVowelPattern(query))) {
                result[i] = vowelPattern[GetVowelPattern(query)];
            } else {
                result[i] = "";
            }
        }
        
        return result;
    }
}

var spellchecker = function(wordlist, queries) {
    const exact = new Set(wordlist);
    const lowercase = new Map();
    const vowelPattern = new Map();
    
    const getVowelPattern = (s) => {
        return s.toLowerCase().replace(/[aeiou]/g, '*');
    };
    
    for (const word of wordlist) {
        const lower = word.toLowerCase();
        if (!lowercase.has(lower)) {
            lowercase.set(lower, word);
        }
        
        const pattern = getVowelPattern(word);
        if (!vowelPattern.has(pattern)) {
            vowelPattern.set(pattern, word);
        }
    }
    
    const result = [];
    for (const query of queries) {
        if (exact.has(query)) {
            result.push(query);
        } else if (lowercase.has(query.toLowerCase())) {
            result.push(lowercase.get(query.toLowerCase()));
        } else if (vowelPattern.has(getVowelPattern(query))) {
            result.push(vowelPattern.get(getVowelPattern(query)));
        } else {
            result.push("");
        }
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(N + M)，其中 N 是 wordlist 长度，M 是 queries 长度
空间复杂度	O(N)，用于存储三个哈希表

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析