算法学习day4--字母异位词哈希计数解法

算法学习day4–字母异位词哈希计数解法

引入

「有效的字母异位词」是哈希计数思想的入门经典题：给定两个字符串 s 和 t，判断 t 是否是 s 的字母异位词——即两个字符串包含的字母种类和数量完全相同，只是顺序可能不同。例如 listen 和 silent 是异位词，rat 和 car 不是。

这道题本身不难，但它示范了一个高频套路：「判断组成是否相同」类问题，优先考虑频次统计。学会之后，“找字符串中第一个只出现一次的字符”、“两个数组的交集”、" ransom note 能否由杂志字母拼出" 等一系列题都是同一个思路的变体。

先想暴力：排序对齐

最直觉的解法：如果两个串是异位词，那把字符排序后一定完全相等。

fun isAnagramSort(s: String, t: String): Boolean {
if (s.length != t.length) return false
return s.toCharArray().sorted().joinToString("") ==
t.toCharArray().sorted().joinToString("")
}

• 正确性没问题；
• 复杂度是 O(n log n) 时间（排序主导）、O(n) 额外空间。
• 瓶颈在于：我们其实不需要知道「字母的顺序关系」，只需要「每个字母出现了几次」。排序做了大量无用功——这正是优化的切入点。

更优解：数组频次计数

小写字母只有 26 种，用一个长度 26 的数组当计数器即可：

fun isAnagram(s: String, t: String): Boolean {
if (s.length != t.length) return false

val count = IntArray(26)
for (c in s) count[c – 'a']++ // s 的字母 +1
for (c in t) count[c – 'a']— // t 的字母 -1

return count.all { it == 0 } // 全为 0 说明频次完全抵消
}

思路拆解：

也可以写成一次遍历的版本（下标从 0 走到 n，同时加 s[i] 减 t[i]），逻辑等价。

复杂度与解法对比

工程上的取舍：题目限定小写字母时数组计数是最优解；如果字符可能是任意 Unicode（中文、emoji），26 长度数组不够，应换成 HashMap<Char, Int> 计数——思想完全相同，只是容器从数组换成哈希表。

一个细节：如果这题改成「找出 s 中 t 的所有异位词起始下标」（LeetCode 438），就还要在计数数组上做滑动窗口增量更新，而不是每次重建计数——这也是计数思想往中档题进阶的方向。

实际场景

• 敏感词/相似度检测：判断两段文本用词组成是否一致（打乱顺序规避检测的场景）；
• 数据校验：校验重排后的日志行是否丢失/多出内容（频次 diff）；
• 缓存键归一化：把「组成相同」的对象归一到同一个 key，比如把字母集合排序后作为分组键（LeetCode 49 字母异位词分组就是干这个）。

可迁移套路

这题提炼出的可迁移套路一句话：「比较组成而不比较顺序 → 频次统计」。

具体动手模板：

后续的「 ransom note 」（单向频次扣减）、「第一个只出现一次的字符」（频次 + 首次位置）、「字母异位词分组」（排序串作哈希键）都是这个模板的直接应用。

小结

• 有效的字母异位词 = 两个串字母频次完全相同；
• 排序法 O(n log n) 是直觉解；数组计数法 O(n) + O(1) 空间才是最优解；
• 关键技巧：c – 'a' 做字符到下标的映射；先判长度做剪枝；
• 核心套路「比较组成 → 频次统计」，字符集大时把数组换成哈希表即可平移到更复杂的题目上。