LC242. 有效的字母异位词

题目描述

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。 注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。 示例 1: 输入: s = "anagram", t = "nagaram" 输出: true 示例 2: 输入: s = "rat", t = "car" 输出: false 提示: 1 <= s.length, t.length <= 5 * 104 s 和 t 仅包含小写字母 进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

题目解析

题目在说什么

这道题让你判断两个字符串是不是“字母异位词”。听起来有点绕口，其实很简单：就是看两个字符串里用的字母是不是一模一样，每个字母出现的次数也一样，只是顺序可以不同。比如：

• s = "anagram"，t = "nagaram"：s 里有 3 个 a、1 个 n、1 个 g、1 个 r、1 个 m，t 里也是这些字母、同样次数，只是顺序乱了，所以是字母异位词。
• s = "rat"，t = "car"：s 里有 r、a、t，t 里有 c、a、r，多了个 c 少了 t，次数不匹配，所以不是。

题目还给了个提示：字符串只包含小写字母（a 到 z），长度最多 5 万。这很重要，因为小写字母只有 26 个，我们可以用简单的方法处理。

思路是怎么来的

想象一下，你有一盒积木，上面写着字母。s 字符串就是一堆积木，t 是另一堆。你想知道这两堆积木是不是完全一样（字母种类和数量都相同），只是摆放顺序不同。

你会怎么做？最直接的办法是：把 s 里的每个字母数一遍，记下每个字母有几个；然后数 t 里的字母，对比一下。如果每个字母的数量都一样，那就是字母异位词。

但怎么“记下来”呢？因为只有 26 个小写字母，我们可以用一个“计数器”数组，它有 26 个格子，每个格子对应一个字母（比如格子 0 对应 a，格子 1 对应 b，……，格子 25 对应 z）。然后：

• 先遍历 s，每遇到一个字母，就在对应的格子里加 1。
• 再遍历 t，每遇到一个字母，就在对应的格子里减 1。
• 如果最后所有格子都变回 0，说明 s 和 t 的字母种类和数量完全一样；如果中间某个格子变成负数（说明 t 里这个字母比 s 多），或者最后有格子不是 0，那就不是。

这个思路就像：你有一本账本，s 是收入，t 是支出，最后收支平衡就是字母异位词。

代码逐步拆解

我们来看参考代码，一行一行讲清楚。

class Solution {
    public boolean isAnagram(String s, String t) {
        // 第一步：长度不同，直接返回 false
        if(s.length() != t.length()){
            return false;
        }

为什么？ 如果两个字符串长度不一样，说明字母总数不同，肯定不是字母异位词。比如 s 有 5 个字母，t 有 6 个，那无论如何都不可能每个字母次数相同。这是最简单的一步，先排除掉。

        // 第二步：创建一个长度为 26 的数组，用来记录每个字母出现的次数
        int[] table = new int[26];

为什么是 26？ 因为题目说只包含小写字母，a 到 z 正好 26 个。数组的每个位置（索引 0 到 25）对应一个字母。比如索引 0 对应 a，索引 1 对应 b，……，索引 25 对应 z。

        // 第三步：遍历字符串 s，统计每个字母出现的次数
        for( int i = 0 ; i < s.length() ; i++){
            int index = s.charAt(i) - 'a';
            table[index]++;
        }

这里在做什么？ s.charAt(i) 取出 s 中第 i 个字符，比如 'a' 或 'b'。然后 s.charAt(i) - 'a' 把字母转成数字：'a' - 'a' = 0，'b' - 'a' = 1，……，'z' - 'a' = 25。这样就能知道这个字母对应数组的哪个格子。然后 table[index]++ 让那个格子里的数字加 1，表示这个字母出现了一次。

比如 s = "anagram"，遍历完：

• a 出现 3 次 → table[0] = 3
• n 出现 1 次 → table[13] = 1（n 是第 14 个字母，索引 13）
• g 出现 1 次 → table[6] = 1
• r 出现 1 次 → table[17] = 1
• m 出现 1 次 → table[12] = 1

        // 第四步：遍历字符串 t，每遇到一个字母就减少对应格子里的次数
        for( int i = 0 ; i < t.length() ; i++){
            int index = t.charAt(i) - 'a';
            table[index]--;
            // 如果某个格子变成负数，说明 t 里这个字母比 s 多，直接返回 false
            if(table[index] < 0){
                return false;
            }
        }

为什么减？ 因为我们要“抵消” s 里统计的次数。如果 t 里也有同样的字母，次数就会减回 0。如果 t 里某个字母出现次数比 s 多，那这个格子就会变成负数，说明 t 里多出了 s 没有的字母（或者数量多了），直接返回 false。

比如 t = "nagaram"，遍历：

• n → table[13] 从 1 减到 0
• a → table[0] 从 3 减到 2
• g → table[6] 从 1 减到 0