LeetCode 242. 有效的字母异位词

2026-04-16 HGNULB 约 6 分钟

文章信息 14 个分类 3 个标签

分类

LeetCode CodeTop 简单未解决 10-20 面试经典 150 题腾讯字节微软亚马逊美团小米网易猿辅导

题目描述

✅ 242. 有效的字母异位词

题意分析

字母异位词只要求每种字符的出现次数相同，不要求排列顺序不同，因此两个完全相同的字符串也符合条件。只比较出现过哪些字符还不够，重复次数也必须一致。

基础题限定小写英文字母，可以用长度为 26 的数组计数；题面进阶允许 Unicode 字符，需要把计数单位改为码点，并用哈希表记录频次。

解法：字母频次差计数

核心思路

[!blue]

如果每种字母的数量都相同，总长度也必然相同，因此先排除长度不同的情况。

用 count[c] 保存字母 c 在 s 中的出现次数减去在 t 中的出现次数。扫描到 s 的字母就加一，扫描到 t 的字母就减一，相当于把两张频次表的比较合并到一张差值表中。

遍历结束后，所有差值为零，说明每种字母都能一一配对；只要有一个差值非零，就说明某种字母的数量不同。同步扫描时，中途的差值只能反映已经读过的前缀，后续字符仍可能抵消它，所以不能提前根据正负判断结果。

解题步骤

若 s 与 t 的长度不同，直接返回 false。

建立初始值全为 0 的数组 count，将字母 c 映射到下标 c - 'a'。

同时遍历两个字符串，对 s[i] 对应项加一，对 t[i] 对应项减一。

遍历全部 26 个差值：只要存在非零值就返回 false，全部为零则返回 true。

代码实现

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$。

关键点总结

[!green]

判断依据是每种字母的数量，而不是顺序或字符集合。

差值数组把“两份数量是否相等”变成“每一项是否归零”。

小写英文字母的种类固定，才能用定长数组代替哈希表。

解法二：Unicode 码点频次差计数

核心思路

[!blue]

差值计数的判定不变，只把数组下标换成 Unicode 码点。字符种类不再限定为 26 个，用哈希表按实际出现的码点保存差值即可。

Java 的一个 char 是一个 UTF-16 编码单元，部分字符需要两个 char 表示。用 codePointAt(i) 读取完整码点，再通过 Character.charCount(codePoint) 决定前进一位还是两位。Go 的字符串按下标取到的是字节，使用 range 才会按 Unicode 码点解码，得到 rune。

分别遍历 s 和 t，对码点计数加一、减一，最后检查全部差值是否为零。这种遍历不依赖两个字符串的编码长度相同。这里按码点判断字符是否相同，不额外合并视觉相同但码点序列不同的写法。

解题步骤

建立“码点 → 频次差”的哈希表。

按完整码点遍历 s，将对应计数加一。

按完整码点遍历 t，将对应计数减一；未出现过的码点从 0 开始。

所有计数均为 0 时返回 true，否则返回 false。

代码实现

class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Integer, Integer> count = new HashMap<>();

        for (int i = 0; i < s.length(); ) {
            int codePoint = s.codePointAt(i);
            count.put(codePoint, count.getOrDefault(codePoint, 0) + 1);
            i += Character.charCount(codePoint);
        }

        for (int i = 0; i < t.length(); ) {
            int codePoint = t.codePointAt(i);
            count.put(codePoint, count.getOrDefault(codePoint, 0) - 1);
            i += Character.charCount(codePoint);
        }

        for (int value : count.values()) {
            if (value != 0) {
                return false;
            }
        }

        return true;
    }
}

func isAnagram(s string, t string) bool {
    count := make(map[rune]int)
    for _, codePoint := range s {
        count[codePoint]++
    }
    for _, codePoint := range t {
        count[codePoint]--
    }
    for _, value := range count {
        if value != 0 {
            return false
        }
    }
    return true
}

复杂度分析

时间复杂度：平均 $O(n + m)$，n、m 分别是两个字符串的码点数，哈希表单次操作平均为 $O(1)$。

空间复杂度：$O(k)$，k 是两个字符串中不同码点的总数。

关键点总结

[!green]

Unicode 进阶改变的是字符的读取方式与计数容器，频次差归零的证明仍然成立。

Java 按码点长度推进下标，Go 使用 range 读取 rune，才能把补充字符作为一个完整单位计数。

易错点总结

[!yellow]

同步访问两个字符串前要检查长度，否则可能越界或漏掉多余字符。

中途差值为负不代表数量最终不匹配；当前代码必须处理完整个字符串后再检查。

本题允许两个字符串完全相同，不要额外要求 s 与 t 不相等。

c - 'a' 只适用于小写英文字母。Unicode 进阶不能继续使用长度为 26 的数组，也不能按字节或 UTF-16 编码单元计数。

相似题目

题目	难度	关联与区别
49. 字母异位词分组	中等	两串频次相等的判定可以转成规范签名，用来对多个单词分组。
LCR 032. 有效的字母异位词	简单	LCR变体额外要求两个字符串不完全相同，本题相同字符串也属于有效异位词判定范围。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/40370681

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！