LeetCode 面试题 01.02. 判定是否互为字符重排

约 5 分钟
文章信息 3 个分类 3 个标签
分类
LeetCode 简单 程序员面试金典（第 6 版）
标签
字符串 哈希表 排序
目录

题目描述

✅ 面试题 01.02. 判定是否互为字符重排

题意分析

给定两个只含小写英文字母的字符串，判断能否只通过重新排列字符，把 s1 变成 s2。重排只能改变位置，不能增加、删除或替换字符，因此答案只取决于两件事：长度是否相同，以及每个字母出现的次数是否相同。

重复字符不能忽略。"aab" 与 "abb" 使用的字符种类都是 {a,b}，但频次不同，不能互相重排；所以集合只能判断“出现过什么”，不足以解决本题。

题目把字符集限定为 26 个小写字母，这是用定长数组代替哈希表的直接信号。若面试官把输入放宽为任意 Unicode 字符，算法不变，只需把 int[26] 换成字符到次数的映射。

解法：定长数组统计字符频次

核心思路

排序后逐位比较可以解决问题，但需要 $O(n \log n)$ 时间，还可能创建额外字符数组。既然字符集只有 26 个字母，更直接的做法是统计频次：遍历 s1 时加一，遍历 s2 时减一。

第二次遍历的不变量是：处理完 s2[0..i] 后，cnt[c] 表示 s1 中字符 c 的总数，减去 s2 已处理前缀使用的数量。一旦某个计数变成负数，说明 s2 对这个字符的需求已经超过 s1 的供给，可以立即返回 false。

为什么最后不必再扫描一次 cnt？入口已经保证两个字符串等长。如果所有字符都没有被多减，那么 s2 总共消耗了与 s1 完全相同数量的字符，不可能还有某个计数为正；否则总和无法回到零。

解题步骤

  • 先比较长度，不相等直接返回 false。这一步既是必要条件，也让后面的“没有负数即可成功”成立。
  • 建立长度为 26 的计数数组，遍历 s1，用 c - 'a' 映射下标并加一。
  • 遍历 s2，对对应计数先减一；若结果小于零，立即返回 false。
  • 第二次遍历结束仍未失败，返回 true。

以 s1 = "aabc"、s2 = "abca" 为例。统计 s1 后，a、b、c 的次数分别是 2、1、1；按 a、b、c、a 的顺序扣减后依次回到 0、0、0，答案为 true。若 s2 = "abbc"，处理第二个 b 时其计数从 0 变成 -1，当场判定为 false。

代码实现

// cnt 表示 s1 的字符供给减去 s2 已消费的数量。
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : s1.toCharArray()) {
            ++cnt[c - 'a'];
        }
        for (char c : s2.toCharArray()) {
            if (--cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

// cnt 表示 s1 的字符供给减去 s2 已消费的数量。
func CheckPermutation(s1 string, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }
    cnt := make([]int, 26)
    for _, c := range s1 {
        cnt[c-'a']++
    }
    for _, c := range s2 {
        if cnt[c-'a']--; cnt[c-'a'] < 0 {
            return false
        }
    }
    return true
}

复杂度分析

  • 时间复杂度：$O(n + m)$，其中 n、m 分别是两个字符串的长度；长度相等时可简写为 $O(n)$。
  • 空间复杂度：$O(1)$，计数数组固定为 26 个整数，不随输入长度增长。

关键点总结

  • “能否重排得到”应立刻翻译成“字符多重集合是否相等”，字符顺序完全不重要，频次才是状态。
  • 小字符集优先用定长数组；字符集未知或很大时再换哈希表。
  • 面试表达时先说长度剪枝，再给出“加一 / 减一，负数提前失败”的不变量，代码就只剩两个线性循环。
  • 常见追问是“能否排序解决”：可以，时间 $O(n \log n)$；计数法利用了小写字母约束，时间更优且不修改输入。

易错点总结

  • 只比较字符集合，不比较次数：s1 = "aab"、s2 = "abb" 的集合相同，却不能重排得到。
  • 漏掉长度判断，又只在减成负数时失败：s1 = "ab"、s2 = "a" 不会出现负数，错误返回 true。
  • 第二轮先判断再减一：当某字符的剩余次数恰为 0 时还会放行一次。应先减一，再检查是否小于零。
  • 忽略题目的字符集约束：若输入可能含大写字母或 Unicode，直接用 c - 'a' 会越界；此时应改用映射。

相似题目

题目 难度 考察点
49. 字母异位词分组 中等 字符计数
242. 有效的字母异位词 简单 字符计数
383. 赎金信 简单 字符计数
387. 字符串中的第一个唯一字符 简单 字符计数
451. 根据字符出现频率排序 中等 字符计数
LCR 032. 有效的字母异位词 简单 字符计数
LCR 033. 字母异位词分组 中等 字符计数
剑指 Offer 50. 第一个只出现一次的字符 简单 字符计数
面试题 01.01. 判定字符是否唯一 简单 字符计数
面试题 01.04. 回文排列 简单 字符计数
面试题 10.02. 变位词组 中等 字符计数