LeetCode-Go 题解：966. Vowel Spellchecker 元音拼写检查器的三表哈希实现

LeetCode-Go 题解：966. Vowel Spellchecker 元音拼写检查器的三表哈希实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南以 leetcode/0966.Vowel-Spellchecker/README.md 为核心骨架，完整剖析 LeetCode 第 966 题《Vowel Spellchecker》（元音拼写检查器）的题意、四层匹配优先级规则，并结合 966. Vowel Spellchecker.go 的源码逐行讲解"三张哈希表 + 元音掩码"的解题方案。读完本文，你将掌握如何用 Go 以 O((N+Q)×L) 的时间复杂度实现一个可处理大小写错误与元音错误的分层拼写检查器，并理解其与配套单测 966. Vowel Spellchecker_test.go 之间的验证关系。

题目背景与问题定义

LeetCode 966 要求实现一个拼写检查器：给定一个单词列表wordlist和若干查询单词queries，对每个查询query，从wordlist中找出"正确"的单词并返回；若找不到任何匹配，则返回空字符串""。

题目约束（继承自原文档）：

• 1 <= wordlist.length <= 5000
• 1 <= queries.length <= 5000
• 1 <= wordlist[i].length <= 7
• 1 <= queries[i].length <= 7
• wordlist与queries中的所有字符串仅由英文字母组成

由于单词长度上限仅为 7，单次匹配成本极低，问题真正的难点在于正确组织多层匹配规则，而不是暴力扫描。

拼写检查处理的两类错误

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

1. 大小写错误（Capitalization）

如果query与wordlist中的某个单词不区分大小写地相等，则返回wordlist中该单词的原始大小写形式。原文档给出了三个例子：

• wordlist = ["yellow"]，query = "YellOw"→correct = "yellow"
• wordlist = ["Yellow"]，query = "yellow"→correct = "Yellow"
• wordlist = ["yellow"]，query = "yellow"→correct = "yellow"

2. 元音错误（Vowel Errors）

如果将query中的元音字母（'a'、'e'、'i'、'o'、'u'）各自替换为任意元音后，能与wordlist中的某个单词（不区分大小写）匹配，则返回该单词的原始形式。注意这里的"替换"是逐一替换且元音之间互相等价，而不是插入或删除元音，因此元音数量必须一致。原文档的例子：

• wordlist = ["YellOw"]，query = "yollow"→correct = "YellOw"（e与o互换位置不改变掩码）
• wordlist = ["YellOw"]，query = "yeellow"→correct = ""（元音数量不同，掩码不匹配）
• wordlist = ["YellOw"]，query = "yllw"→correct = ""（缺失元音，掩码不匹配）

四条匹配优先级规则

除上述两类错误外，题目还明确规定了匹配的优先级（原文档原文要点）：

1. 当query与wordlist中某个单词区分大小写地完全一致时，直接返回该单词本身；
2. 否则，若query仅存在大小写差异，返回wordlist中第一个这样的匹配项；
3. 否则，若query存在元音错误，返回wordlist中第一个这样的匹配项；
4. 若以上均不满足，返回空字符串""。

优先级决定了匹配顺序必须是"精确匹配 → 大小写归一匹配 → 元音掩码匹配"的逐级降级过程，一旦命中即返回，不再尝试更低级别。

官方示例推演

原文档给出的示例为：

Input: wordlist = ["KiTe","kite","hare","Hare"] queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"] Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

逐条推演：

这个推演过程同时验证了"元音错误"的边界：Hear之所以失败，是因为ea是两个元音，而hare只有一个元音，掩码长度对不上。

解题思路：三张哈希表的层次化匹配

原文档的解题思路明确指出"很明显需要用map来解题"，并归纳为三种情况：

1. 查询字符串完全匹配：用map[string]bool记录wordlist中的原始单词，key直接命中即返回；
2. 查询字符串仅大小写不同：用map[string]string将单词的小写形式映射回原单词的正确大小写形式；
3. 查询字符串有元音错误：用map[string]string将单词忽略元音的小写形式映射回原单词的正确形式。

这里的关键设计是**"只保留第一个匹配"：题目要求返回wordlist中第一个匹配项，因此在构建wordsCap与wordsVowel两张映射表时，只有当某个归一化键首次出现**时才写入，之后重复出现不再覆盖，从而天然保证"第一个匹配优先"。

其源码实现在 966. Vowel Spellchecker.go 中，核心数据结构如下：

wordsPerfect, wordsCap, wordsVowel := map[string]bool{}, map[string]string{}, map[string]string{}

• wordsPerfect：精确匹配表（区分大小写）；
• wordsCap：大小写归一表（键为小写单词）；
• wordsVowel：元音掩码表（键为去掉元音特征的小写单词）。

Go 实现逐步解析

第一步：预处理wordlist，构建三张表

for _, word := range wordlist { wordsPerfect[word] = true wordLow := strings.ToLower(word) if _, ok := wordsCap[wordLow]; !ok { wordsCap[wordLow] = word } wordLowVowel := devowel(wordLow) if _, ok := wordsVowel[wordLowVowel]; !ok { wordsVowel[wordLowVowel] = word } }

• wordsPerfect[word] = true：原样收录，用于第一级精确匹配；
• strings.ToLower(word)得到小写形式，作为第二级匹配的键；
• devowel(wordLow)得到元音掩码形式，作为第三级匹配的键；
• 两处if _, ok := ...; !ok判断保证只保留第一次出现的单词，对应题目"返回第一个匹配项"的规则。这是整个实现中容易被忽略却至关重要的细节。

第二步：逐条处理查询，按优先级降级

res, index := make([]string, len(queries)), 0 for _, query := range queries { if _, ok := wordsPerfect[query]; ok { res[index] = query index++ continue } queryL := strings.ToLower(query) if v, ok := wordsCap[queryL]; ok { res[index] = v index++ continue } queryLV := devowel(queryL) if v, ok := wordsVowel[queryLV]; ok { res[index] = v index++ continue } res[index] = "" index++ } return res

匹配流程严格对应四条优先级规则：

1. wordsPerfect[query]命中 → 返回原query（精确匹配）；
2. 小写化后查wordsCap命中 → 返回wordlist中的原始大小写（大小写归一）；
3. 小写化再元音掩码后查wordsVowel命中 → 返回原始单词（元音错误修正）；
4. 全部未命中 → 写入空字符串。

由于预先分配了make([]string, len(queries))并用index递增写入，避免了反复append造成的扩容开销，从源码结构看这是一种面向性能的写法。

devowel：元音掩码的实现细节

func devowel(word string) string { runes := []rune(word) for k, c := range runes { if c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' { runes[k] = '*' } } return string(runes) }

devowel将字符串先转换为[]rune再逐字符判断是否为小写元音a/e/i/o/u，命中则替换为占位符'*'。这样，所有元音无论实际是什么字母，都被归一到同一个占位符，从而把"元音之间互相等价"的题意精确建模为字符串相等比较。

需要说明的是：wordlist与queries均只含英文字母，且本实现先经过strings.ToLower归一，因此devowel中只需判断小写元音即可；采用[]rune而非直接对string做下标替换，从代码结构上看是为了按字符而非按字节处理，使掩码逻辑更稳健、更易扩展到非纯 ASCII 场景。

例如：

• KiTe→ 小写kite→ 掩码k*t*
• keti→ 小写keti→ 掩码k*t*→ 与前者相等，故query = "keti"能命中KiTe

复杂度分析

设wordlist长度为 N，queries长度为 Q，单词最大长度为 L（本题约束 L ≤ 7）：

• 预处理阶段：遍历 N 个单词，每个单词做一次小写转换与一次掩码转换，时间复杂度 O(N×L)，空间上三张表合计存储 O(N×L) 个字符；
• 查询阶段：每个查询执行一次精确查表、一次小写转换查表、一次掩码转换查表，时间复杂度 O(Q×L)；
• 总体复杂度：O((N+Q)×L) 时间，O(N×L) 空间，完全满足 5000×7 量级的数据规模，且每个查询的匹配都是哈希表 O(1) 级别的常数操作，无需对wordlist做任何二次扫描。

测试与验证

仓库为本题提供了完整单测 966. Vowel Spellchecker_test.go，其中Test_Problem966将官方示例作为唯一用例执行验证：

qs := []question966{ { para966{[]string{"KiTe", "kite", "hare", "Hare"}, []string{"kite", "Kite", "KiTe", "Hare", "HARE", "Hear", "hear", "keti", "keet", "keto"}}, ans966{[]string{"kite", "KiTe", "KiTe", "Hare", "hare", "", "", "KiTe", "", "KiTe"}}, }, }

该用例同时覆盖了精确匹配、大小写归一、元音错误修正与空结果四种路径，是验证题目四条优先级规则是否落实的直接依据。

本地运行该用例的命令为：

go test -v -run Test_Problem966 ./leetcode/0966.Vowel-Spellchecker/

若需对整个题解仓库生成覆盖率报告，可复用 gotest.sh 中的方式（该脚本以atomic模式对全部leetcode包一次性产出合法覆盖率文件）：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

注意运行前提：本仓库go.mod声明的 Go 版本为go 1.19，执行上述命令需要本地安装与之兼容的 Go 工具链。

小结

LeetCode 966 是一道"规则驱动型"的字符串处理题，其核心并不在算法技巧，而在于如何把四条优先级规则映射为可判定的键。本题的 Go 解法给出了一个简洁且可迁移的范式：

• 用map[string]bool承载精确匹配；
• 用"小写键 → 原词"的映射承载大小写归一；
• 用"元音掩码键 → 原词"的映射承载元音错误修正；
• 构建时"只保留首个匹配"，查询时"逐级降级、命中即返"。

结合 966. Vowel Spellchecker.go 的源码与 966. Vowel Spellchecker_test.go 的单测，这一"三表哈希 + 掩码归一"的思路不仅适用于本题，也可推广到任何"多级模糊匹配且需要保留首个命中"的检索场景，例如搜索建议、同音词纠错、词典近似查询等。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go