尧图网站建设 
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((NQ)×L) 的时间复杂度实现一个可处理大小写错误与元音错误的分层拼写检查器并理解其与配套单测 966. Vowel Spellchecker_test.go 之间的验证关系。题目背景与问题定义LeetCode 966 要求实现一个拼写检查器给定一个单词列表wordlist和若干查询单词queries对每个查询query从wordlist中找出正确的单词并返回若找不到任何匹配则返回空字符串。题目约束继承自原文档1 wordlist.length 50001 queries.length 50001 wordlist[i].length 71 queries[i].length 7wordlist与queries中的所有字符串仅由英文字母组成由于单词长度上限仅为 7单次匹配成本极低问题真正的难点在于正确组织多层匹配规则而不是暴力扫描。拼写检查处理的两类错误对于给定的查询单词query拼写检查器只处理两类拼写错误1. 大小写错误Capitalization如果query与wordlist中的某个单词不区分大小写地相等则返回wordlist中该单词的原始大小写形式。原文档给出了三个例子wordlist [yellow]query YellOw→correct yellowwordlist [Yellow]query yellow→correct Yellowwordlist [yellow]query yellow→correct yellow2. 元音错误Vowel Errors如果将query中的元音字母a、e、i、o、u各自替换为任意元音后能与wordlist中的某个单词不区分大小写匹配则返回该单词的原始形式。注意这里的替换是逐一替换且元音之间互相等价而不是插入或删除元音因此元音数量必须一致。原文档的例子wordlist [YellOw]query yollow→correct YellOwe与o互换位置不改变掩码wordlist [YellOw]query yeellow→correct 元音数量不同掩码不匹配wordlist [YellOw]query yllw→correct 缺失元音掩码不匹配四条匹配优先级规则除上述两类错误外题目还明确规定了匹配的优先级原文档原文要点当query与wordlist中某个单词区分大小写地完全一致时直接返回该单词本身否则若query仅存在大小写差异返回wordlist中第一个这样的匹配项否则若query存在元音错误返回wordlist中第一个这样的匹配项若以上均不满足返回空字符串。优先级决定了匹配顺序必须是精确匹配 → 大小写归一匹配 → 元音掩码匹配的逐级降级过程一旦命中即返回不再尝试更低级别。官方示例推演原文档给出的示例为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]逐条推演query命中级别返回原因kite精确匹配kite与wordlist[1]完全一致Kite大小写归一KiTe小写化后为kite返回wordlist中第一个小写为kite的词即KiTeKiTe精确匹配KiTe与wordlist[0]完全一致Hare精确匹配Hare与wordlist[2]完全一致HARE大小写归一hare小写化后为hare返回第一个匹配项hareHear元音掩码掩码化后为h**r而hare/Hare掩码为h*r*不匹配hear元音掩码同上掩码h**r与h*r*不一致keti元音掩码KiTe掩码化后为k*t*与KiTe的掩码k*t*一致keet元音掩码掩码为k**t元音数量与k*t*不一致keto元音掩码KiTe掩码k*t*与KiTe一致o与i同为元音这个推演过程同时验证了元音错误的边界Hear之所以失败是因为ea是两个元音而hare只有一个元音掩码长度对不上。解题思路三张哈希表的层次化匹配原文档的解题思路明确指出很明显需要用map来解题并归纳为三种情况查询字符串完全匹配用map[string]bool记录wordlist中的原始单词key直接命中即返回查询字符串仅大小写不同用map[string]string将单词的小写形式映射回原单词的正确大小写形式查询字符串有元音错误用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匹配流程严格对应四条优先级规则wordsPerfect[query]命中 → 返回原query精确匹配小写化后查wordsCap命中 → 返回wordlist中的原始大小写大小写归一小写化再元音掩码后查wordsVowel命中 → 返回原始单词元音错误修正全部未命中 → 写入空字符串。由于预先分配了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长度为 Nqueries长度为 Q单词最大长度为 L本题约束 L ≤ 7预处理阶段遍历 N 个单词每个单词做一次小写转换与一次掩码转换时间复杂度 O(N×L)空间上三张表合计存储 O(N×L) 个字符查询阶段每个查询执行一次精确查表、一次小写转换查表、一次掩码转换查表时间复杂度 O(Q×L)总体复杂度O((NQ)×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 -covermodeatomic -coverprofilecoverage.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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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((NQ)×L) 的时间复杂度实现一个可处理大小写错误与元音错误的分层拼写检查器并理解其与配套单测 966. Vowel Spellchecker_test.go 之间的验证关系。题目背景与问题定义LeetCode 966 要求实现一个拼写检查器给定一个单词列表wordlist和若干查询单词queries对每个查询query从wordlist中找出正确的单词并返回若找不到任何匹配则返回空字符串。题目约束继承自原文档1 wordlist.length 50001 queries.length 50001 wordlist[i].length 71 queries[i].length 7wordlist与queries中的所有字符串仅由英文字母组成由于单词长度上限仅为 7单次匹配成本极低问题真正的难点在于正确组织多层匹配规则而不是暴力扫描。拼写检查处理的两类错误对于给定的查询单词query拼写检查器只处理两类拼写错误1. 大小写错误Capitalization如果query与wordlist中的某个单词不区分大小写地相等则返回wordlist中该单词的原始大小写形式。原文档给出了三个例子wordlist [yellow]query YellOw→correct yellowwordlist [Yellow]query yellow→correct Yellowwordlist [yellow]query yellow→correct yellow2. 元音错误Vowel Errors如果将query中的元音字母a、e、i、o、u各自替换为任意元音后能与wordlist中的某个单词不区分大小写匹配则返回该单词的原始形式。注意这里的替换是逐一替换且元音之间互相等价而不是插入或删除元音因此元音数量必须一致。原文档的例子wordlist [YellOw]query yollow→correct YellOwe与o互换位置不改变掩码wordlist [YellOw]query yeellow→correct 元音数量不同掩码不匹配wordlist [YellOw]query yllw→correct 缺失元音掩码不匹配四条匹配优先级规则除上述两类错误外题目还明确规定了匹配的优先级原文档原文要点当query与wordlist中某个单词区分大小写地完全一致时直接返回该单词本身否则若query仅存在大小写差异返回wordlist中第一个这样的匹配项否则若query存在元音错误返回wordlist中第一个这样的匹配项若以上均不满足返回空字符串。优先级决定了匹配顺序必须是精确匹配 → 大小写归一匹配 → 元音掩码匹配的逐级降级过程一旦命中即返回不再尝试更低级别。官方示例推演原文档给出的示例为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]逐条推演query命中级别返回原因kite精确匹配kite与wordlist[1]完全一致Kite大小写归一KiTe小写化后为kite返回wordlist中第一个小写为kite的词即KiTeKiTe精确匹配KiTe与wordlist[0]完全一致Hare精确匹配Hare与wordlist[2]完全一致HARE大小写归一hare小写化后为hare返回第一个匹配项hareHear元音掩码掩码化后为h**r而hare/Hare掩码为h*r*不匹配hear元音掩码同上掩码h**r与h*r*不一致keti元音掩码KiTe掩码化后为k*t*与KiTe的掩码k*t*一致keet元音掩码掩码为k**t元音数量与k*t*不一致keto元音掩码KiTe掩码k*t*与KiTe一致o与i同为元音这个推演过程同时验证了元音错误的边界Hear之所以失败是因为ea是两个元音而hare只有一个元音掩码长度对不上。解题思路三张哈希表的层次化匹配原文档的解题思路明确指出很明显需要用map来解题并归纳为三种情况查询字符串完全匹配用map[string]bool记录wordlist中的原始单词key直接命中即返回查询字符串仅大小写不同用map[string]string将单词的小写形式映射回原单词的正确大小写形式查询字符串有元音错误用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匹配流程严格对应四条优先级规则wordsPerfect[query]命中 → 返回原query精确匹配小写化后查wordsCap命中 → 返回wordlist中的原始大小写大小写归一小写化再元音掩码后查wordsVowel命中 → 返回原始单词元音错误修正全部未命中 → 写入空字符串。由于预先分配了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长度为 Nqueries长度为 Q单词最大长度为 L本题约束 L ≤ 7预处理阶段遍历 N 个单词每个单词做一次小写转换与一次掩码转换时间复杂度 O(N×L)空间上三张表合计存储 O(N×L) 个字符查询阶段每个查询执行一次精确查表、一次小写转换查表、一次掩码转换查表时间复杂度 O(Q×L)总体复杂度O((NQ)×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 -covermodeatomic -coverprofilecoverage.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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考