（算法 哈希表）【LeetCode 242】有效的字母异位词

📌 题目链接：242. 有效的字母异位词

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram" 输出: true

示例 2:

输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

思路分析

1. 暴力解法

最直接的思路是双层 for 循环，每次从 s 中取出一个字符去 t 里找是否存在。
这种方法不仅需要额外标记字符是否用过，还会导致时间复杂度达到 O(n^2)，在字符串很长时效率极低。
因此，我们考虑更优的解法。

2. 哈希表解法

为什么用哈希表（数组）？

• 本题的关键在于 统计两个字符串中每个字符出现的次数。

• 我们需要快速完成 字符 → 出现次数 的映射。

• 哈希表（数组）正好适合这种场景。

为什么用数组代替哈希表？

• 因为题目限定了只包含小写字母 'a' ~ 'z'，刚好 26 个字母。

• 我们可以用一个长度为 26 的数组 record 来代替哈希表，效率更高。

• 而Hashmap虽然通用性好，但是针对有限少量数据的数据结构，代码实现复杂度较高，不如用哈希表数组实现。

• record[i] 表示某个字母出现的次数，其中：

  • record[s.charAt(i) - 'a']++ 统计字符串 s

  • record[t.charAt(i) - 'a']-- 抵消字符串 t

最后只要判断 record 中是否所有值都为 0，即可确定两个字符串是否为字母异位词。

动画理解

假设 s = "aee", t = "eae"

1. 遍历 s：

   • a → record[0]++

   • e → record[4]++

   • e → record[4]++
     此时 record[0] = 1, record[4] = 2

2. 遍历 t：

   • e → record[4]--

   • a → record[0]--

   • e → record[4]--
     此时 record[0] = 0, record[4] = 0

最终 record 数组全为 0，说明 s 和 t 是异位词。

代码实现（Java）

class Solution {public boolean isAnagram(String s, String t) {// 长度不同直接返回 falseif (s.length() != t.length()) return false;int[] record = new int[26];// 一边统计 s，一边抵消 tfor (int i = 0; i < s.length(); i++) {record[s.charAt(i) - 'a']++;record[t.charAt(i) - 'a']--;}// 检查所有字母出现次数是否归零for (int i = 0; i < 26; i++) {if (record[i] != 0) return false;}return true;}
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串长度。只需一次遍历即可。

• 空间复杂度：O(1)，只使用了固定大小的数组 record[26]。

方法对比