LeetCode LCR 032. 有效的字母异位词

约 6 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 简单 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
字符串 哈希表 排序 LCR

题目描述

✅ LCR 032. 有效的字母异位词

image-20260928235335038

image-20260928235335040

题意分析

本题的变位词需要同时满足两点：每种字符的出现次数相同，两个字符串的内容又不能完全相同。因此即使频次一致，若 s 与 t 完全相同，也要返回 false。

基础题只含小写英文字母，可以用长度为 26 的数组记录频次。题面进阶允许 Unicode 字符，需要改为按完整码点计数，但“不接受完全相同字符串”的条件仍然保留。

解法：频次差并排除相同字符串

核心思路

[!blue]

先排除长度不同和内容完全相同的情况。频次相同必然要求总长度相同，而内容相同不符合本题定义；通过这两项检查后，只需判断每种字母的次数能否相互抵消。

用 cnt[c - 'a'] 表示字母 c 在 s 中的次数减去在 t 中的次数。同步遍历两串，对 s 的字母加一，对 t 的字母减一，扫描结束后检查所有差值。

每个差值为零，等价于每种字母的数量都相等；任意差值非零就说明数量不匹配。中途的正负值只反映已读前缀，后面的字符仍可能抵消，所以不能在同步扫描中看到负数就提前返回。

解题步骤

  1. 若两串长度不同，或两串内容完全相同，返回 false。
  2. 初始化全零的 26 项数组，将字母映射为 c - 'a'。
  3. 遍历同一下标，对 s 的字母计数加一，对 t 的字母计数减一。
  4. 遍历全部差值；存在非零项时返回 false，全部为零时返回 true。

代码实现

class Solution {
    public boolean isAnagram(String s, String t) {
        int m = s.length();
        int n = t.length();

        // 长度不等必不匹配；完全相同则违反「顺序不完全相同」。
        if (m != n || s.equals(t)) {
            return false;
        }

        // 字符集固定 26 个小写字母，定长数组即可。
        int[] cnt = new int[26];

        for (int i = 0; i < m; ++i) {
            // cnt[k] 的含义：字符 k 在 s 中的次数减去在 t 中的次数。
            ++cnt[s.charAt(i) - 'a'];
            --cnt[t.charAt(i) - 'a'];
        }

        for (int x : cnt) {
            if (x != 0) {
                return false;
            }
        }

        return true;
    }
}

func isAnagram(s string, t string) bool {
    m, n := len(s), len(t)
    // 长度不等必不匹配；完全相同则违反「顺序不完全相同」。
    if m != n || s == t {
        return false
    }
    // 字符集固定 26 个小写字母，定长数组即可。
    cnt := [26]int{}
    for i, c := range s {
        // cnt[k] 的含义：字符 k 在 s 中的次数减去在 t 中的次数。
        cnt[c-'a']++
        cnt[t[i]-'a']--
    }
    for _, x := range cnt {
        if x != 0 {
            return false
        }
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 为字符串长度。内容比较和频次扫描均为线性，最后检查固定 26 项。
  • 空间复杂度：$O(1)$，字符集固定，计数数组大小不随输入长度变化。

关键点总结

[!green]

  • LCR 版本在频次相同之外，还要求字符串内容不同。
  • 差值计数把两份频次是否相等，转成所有计数是否归零。
  • 小写字母限制保证字符可直接映射到固定数组，长度检查保证同步扫描安全。

解法二：Unicode 码点计数

核心思路

[!blue]

字符种类不再限定为 26 个时，用哈希表保存“码点 → 频次差”。先排除两个内容完全相同的字符串，再分别遍历两串，对第一串加一、第二串减一，最后检查是否全部归零。

Java 的一个 char 不一定能表示完整 Unicode 字符，使用 codePointAt(i) 读取码点，再按 Character.charCount 返回的长度推进下标。Go 使用 range 按码点读取，得到 rune，不再把两串的字节下标强行对应。

这里按码点序列判断内容及频次，不额外合并视觉相同但码点表示不同的写法。两串分开扫描，无需假定编码长度相同，频次差会自行检出多余字符。

解题步骤

  1. 两个字符串内容完全相同时，直接返回 false。
  2. 创建码点频次差映射，完整遍历 s 的码点并加一。
  3. 完整遍历 t 的码点并减一，未出现过的键从零开始。
  4. 所有计数都归零时返回 true，否则返回 false。

代码实现

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

        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 {
    if s == t {
        return false
    }
    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(k)$，k 为两串中不同码点的总数。

关键点总结

[!green]

  • 字符读取方式与计数容器改变，频次差归零的判定不变。
  • 仍需先排除相同内容，Unicode 扩展没有改变本题的变位词定义。

易错点总结

[!yellow]

  • 不能直接照搬接受相同字符串的异位词判定，本题需要先排除 s 与 t 内容相同的情况。
  • 要比较出现次数，不能只比较出现过哪些字符。
  • 同步加减时，中途差值可正可负，必须在完整扫描后判断是否全部归零。
  • Unicode 进阶不能继续使用 c - 'a'，也不能把单个字节或半个 UTF-16 代理项当作完整字符。

相似题目

题目 难度 关联与区别
242. 有效的字母异位词 简单 频次判断相同，但本LCR题还要求两个字符串不完全相同；主站题通常接受相同字符串。
49. 字母异位词分组 中等 把两串频次相等的判定扩展为多个字符串按等价签名分组。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/50102030
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！