LeetCode 242. 有效的字母异位词

约 5 分钟
文章信息 14 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 字节跳动 微软 美团 腾讯 猿辅导 网易 小米 亚马逊 面试经典 150 题
标签
字符串 哈希表 排序
目录

题目描述

✅ 242. 有效的字母异位词

image-20230311201533502

题意分析

判断两个字符串是否互为字母异位词，也就是说 t 能否由 s 的全部字符重新排列得到。这等价于一个更好操作的条件：两个字符串每种字符出现的次数完全相同。顺序无关紧要，只有「有哪些字符」和「各出现几次」两件事被考察。

两个约束信号很关键。第一，字符串只包含小写英文字母，字符集大小固定为 $26$，这意味着可以用一个定长数组代替哈希表，查找是 $O(1)$ 的直接下标寻址，空间也算常数。第二，长度可达 $5 \times 10^4$，说明需要线性做法，也说明「先排序再比较」的 $O(n \log n)$ 虽然能过，但不是这题想考的答案。

边界上要注意：长度不同的两个串必然不是异位词，这个判断不仅是优化，也是后续「用同一个下标同时遍历两个串」的前提，缺了它会直接越界。另外两个空串互为异位词，应返回真；两个完全相同的串也互为异位词（题目并不要求排列后与原串不同）。

解法：字母频次差计数

核心思路

异位词只关心每个字符出现多少次，不关心顺序，因此无需排序。题目限定小写英文字母，用长度为 $26$ 的数组即可直接计数。

扫描同一位置时，让 s[i] 对应计数加一、t[i] 对应计数减一。循环结束后数组全为零，当且仅当两串每种字符的频次都相同。长度不同可以立即返回假，同时也是用同一下标遍历两串的前提。

不变量：处理完前 $i$ 个字符后，count[c] 等于字符 c 在 s[0..i) 与 t[0..i) 中的出现次数之差。中途出现非零或负数都不能提前判错，因为后面的字符仍可能将它抵消。

解题步骤

  1. 长度不同，直接返回 false。
  2. 建立长度为 $26$ 的差值数组，字符 c 映射到下标 c - 'a'。
  3. 同时遍历两串：s 的字符加一，t 的字符减一。
  4. 扫描差值数组；存在非零项则返回 false，否则返回 true。

例如 s = "anagram"、t = "nagaram"。扫描中 a、n 等计数会暂时为正或负，但最终全部抵消为零，因此答案为真。

代码实现

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int value : count) {
            if (value != 0) {
                return false;
            }
        }
        return true;
    }
}

func isAnagram(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    count := make([]int, 26)
    for i := 0; i < len(s); i++ {
        count[s[i]-'a']++
        count[t[i]-'a']--
    }
    for _, value := range count {
        if value != 0 {
            return false
        }
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 为字符串长度；末尾检查 $26$ 个计数是常数开销。
  • 空间复杂度：$O(1)$，字符集固定，计数数组长度始终为 $26$。

关键点总结

  • 固定字符集优先用定长数组；排序虽能做，但会把时间提高到 $O(n \log n)$。
  • 一加一减把两张频次表合成一张差值表，最终判据就是「所有差值为零」。
  • 长度检查既是必要条件，也保证同步遍历不会越界。
  • 若字符集扩展到 Unicode，不能再用 c - 'a'，应按码点使用哈希表计数。

易错点总结

  • 忘记先判断长度：同步访问两个字符串时可能越界，也可能漏掉多余字符。
  • 在扫描过程中看到负数就返回假：s = "an"、t = "na" 的计数会暂时为负，但最终能抵消。
  • 只比较出现过哪些字符，不比较次数："aab" 与 "abb" 的字符种类相同，却不是异位词。
  • Java 用 == 比较两个计数数组：比较的是引用，不是数组内容；使用单个差值数组可直接避免这个问题。

相似题目

题目 难度 考察点
49. 字母异位词分组 中等 把频次数组序列化成哈希键，用于分组而非两两比较
383. 赎金信 简单 判据从「差为零」放宽为「差不为负」的单向包含
387. 字符串中的第一个唯一字符 简单 计数后需二次扫描原串以保留首次出现的顺序
451. 根据字符出现频率排序 中等 统计后要按频次排序重建字符串，可用桶排序
LCR 032. 有效的字母异位词 简单 与本题几乎同题，但额外要求两串不能完全相同
LCR 033. 字母异位词分组 中等 与 49 同题，适合对比排序键与计数键两种构造方式
剑指 Offer 50. 第一个只出现一次的字符 简单 与 387 同型，返回字符本身且需处理无解时的占位
面试题 01.01. 判定字符是否唯一 简单 只需存在性而非频次，可用位掩码把空间压到一个整数
面试题 01.02. 判定是否互为字符重排 简单 与本题同解，但字符集扩到 ASCII，数组长度需调整
面试题 01.04. 回文排列 简单 判据变为「出现奇数次的字符至多一个」
面试题 10.02. 变位词组 中等 与 49 同题，考察分组结果的组织与输出