LeetCode 242. Valid Anagram 题解Go 实现字母异位词判断的计数法原理与实战【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 242 题「有效的字母异位词Valid Anagram」展开以本仓库LeetCode-Go中该题的官方题解文档与 Go 源码为骨架完整讲解题目约束、计数打表法的核心思路、两种 Go 实现定长数组计数与哈希表计数、边界条件与测试用例并顺带剖析 Follow up 中 Unicode 场景的适配方案。读完本文你将掌握字母异位词判定的标准套路并能举一反三应用到字母异位词分组等进阶题型中。题目原文与核心考点题目定义如下给定两个字符串s和t编写一个函数判断t是否为s的字母异位词anagram。原题给出的两个示例为Input: s anagram, t nagaram Output: trueInput: s rat, t car Output: false第一组示例中nagaram由anagram的字母重新排列而成a、n、a、g、r、a、m 六个字母逐一对应因此返回true第二组示例中rat与car的字符构成不一致返回false。题目还附带两个重要说明Note可以假设输入字符串仅包含小写字母lowercase alphabets这是选择定长数组解法的前提条件Follow up如果输入包含 Unicode 字符应该如何调整解法题目大意中文释义题解文档给出的中文概括为给出 2 个字符串s和t如果t中的字母在s中都存在输出true否则输出false。更严谨地说字母异位词要求两个字符串长度相同、字符构成完全相同、仅排列顺序不同——这一点从仓库测试用例{, 1}、{a, ab}均返回false可以得到印证。解题思路计数打表法题解文档给出的核心思路是计数打表counting with lookup table流程分三步先建立一个容量为 26 的数组下标依次对应 26 个小写字母0对应a25对应z扫描字符串s每遇到一个字母就在对应下标处加 1再扫描字符串t每遇到一个字母就在对应下标处减 1。如果t是s的字母异位词那么t中每个字母的出现次数必然与s完全一致经过先加后减的抵消后表中所有值都应归零反之只要表中存在非 0 值就说明两个字符串的字符计数不一致输出false。该方法的时间复杂度为 O(n)只需线性扫描两遍字符串且每遍操作均为 O(1) 的数组下标访问空间复杂度为 O(1)固定 26 个整数的数组与输入规模无关。源码实现一定长数组计数小写字母场景仓库解法一实现了上述打表思路完整代码如下见 242. Valid Anagram.go// 解法一 func isAnagram(s string, t string) bool { alphabet : make([]int, 26) sBytes : []byte(s) tBytes : []byte(t) if len(sBytes) ! len(tBytes) { return false } for i : 0; i len(sBytes); i { alphabet[sBytes[i]-a] } for i : 0; i len(tBytes); i { alphabet[tBytes[i]-a]-- } for i : 0; i 26; i { if alphabet[i] ! 0 { return false } } return true }对这段代码的逐步拆解alphabet : make([]int, 26)创建定长计数数组零值即初始计数 0长度预检len(sBytes) ! len(tBytes)长度不同的两个字符串不可能互为字母异位词直接短路返回false省去后续全部扫描sBytes[i]-a利用 ASCII 码连续性把字符a~z映射到数组下标0~25。这也是题目要求仅含小写字母的原因——若输入混入大写字母或数字该偏移计算会越界或错位先对s全体再对t全体--最终遍历 26 个槽位存在非 0 即返回false。源码实现二哈希表计数通用字符场景仓库解法二改用map[rune]int替代定长数组完整代码如下见 242. Valid Anagram.go// 解法二 func isAnagram1(s string, t string) bool { hash : map[rune]int{} for _, value : range s { hash[value] } for _, value : range t { hash[value]-- } for _, value : range hash { if value ! 0 { return false } } return true }与解法一相比这里有两个关键差异按 rune 迭代而非按 byte 迭代range在字符串上迭代时解出的是 Unicode 码点rune天然按字符边界切分不会把多字节 UTF-8 字符拆碎用哈希表动态扩展槽位字符集不再被限制为 26 个小写字母任意 Unicode 字符都能作为 key 计数。这两点使得解法二天然适配题目的 Follow up——当输入包含 Unicode 字符如中文、emoji、带声调字母时只需把解法二中的range改按[]rune(s)迭代即可正确完成计数。这也印证了仓库中解法一、解法二并存的设计意图定长数组解法面向仅小写字母的标准场景追求极致的 O(1) 空间哈希表解法面向通用字符场景保证正确性。测试用例与边界验证仓库测试文件 242. Valid Anagram_test.go 使用表驱动table-driven风格组织用例覆盖了如下关键场景输入s输入t期望输出覆盖的边界true两个空字符串互为异位词1false长度不等 非字母字符anagramnagaramtrue题目示例一正例ratcarfalse题目示例二反例aabfalse长度不等abafalse长度不等长度预检兜底aabbfalse长度相等但字符构成不同其中{aa, bb}用例尤其值得注意它验证了长度相等并不足以判定异位词——两个字符串必须逐字符计数完全一致才行这正是计数表最终校验全 0的意义所在。运行go test执行该测试文件会依次打印每个用例的输入与输出结果全部断言通过仓库目标为 100% 测试覆盖率该题解法一、解法二均被同一测试集覆盖。思路延伸异位词判定在仓库进阶题中的应用字母异位词判定的计数思路在本仓库的进阶题目中有直接延伸。例如 49. Group Anagrams.go 将字符串按 rune 排序后作为哈希 key把互为异位词的字符串归入同一分组——排序后的字符串本质上是字符计数的另一种等价表达两个字符串异位词当且仅当它们排序后相等。该题实现同样通过[]rune(str)处理多字节字符与解法二的 Unicode 兼容策略一脉相承可作为读完本题后的下一道练手题。小结核心结论字母异位词判定等价于字符计数向量相等用一次加、一次减的抵消操作即可在 O(n) 时间内完成适用前提定长 26 数组解法依赖仅含小写字母的题目约束突破该约束时切换为map[rune]int计数即可仓库解法二已给出可直接运行的实现边界意识先做长度预检、再校验计数表全 0两个条件缺一不可仓库测试用例已完整覆盖这两类反例。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考