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

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

题目描述

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

image-20260929004748226

题意分析

判断能否只改变字符顺序，把 s1 变成 s2。字符不能增加、删除或替换，所以两串必须等长，且每种字符出现次数完全相同。题目只含小写英文字母，可以用 26 个计数槽位；重复字符也必须逐个计入。

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

核心思路

[!blue]

重排只关心每种字符有多少个，不关心它们原来的位置。先检查长度，再用 cnt[c - 'a'] 统计 s1 中每个字母的可用数量，随后逐个读取 s2 并扣除对应数量。

第二次遍历时，计数始终等于“s1 中的总数减去 s2 已读取的数量”。先减一再检查；若出现负数，说明目标串已经使用了原串没有的字符数量，之后的字符也无法补回，可以立即返回 false。

扫描结束后，等长条件保证全部计数之和为 0；所有计数又都没有变负，所以每个计数只能等于 0，无需再扫描计数数组。此时各字符数量完全相同，将相同字符分配到目标位置就能完成重排，因此返回 true。两串都为空时也自然成立。

解题步骤

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

代码实现

// 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 (int i = 0; i < s1.length(); i++) {
            ++cnt[s1.charAt(i) - 'a'];
        }

        for (int i = 0; i < s2.length(); i++) {
            if (--cnt[s2.charAt(i) - '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 个整数，不随输入长度增长。

关键点总结

[!green]

  • 重排的充要条件是每种字符频次相同，集合中的字符种类相同还不够。
  • 长度相同且扣减中从未出现负数，才能推出最后所有计数都为零。
  • 定长计数数组依赖题目给定的 26 个小写字母范围。

易错点总结

[!yellow]

  • 只比较字符集合，不比较次数：无法发现同一字母在两串中的数量不同。
  • 漏掉长度判断，又只在减成负数时失败：目标较短时可能仍剩下未用字符，却错误返回 true。
  • 第二轮先判断再减一：当某字符的剩余次数恰为 0 时还会放行一次。应先减一，再检查是否小于零。
  • 把空串当成必定不合法：两串都为空时可以互相重排，结果应为 true。

相似题目

题目 难度 关联与区别
438. 找到字符串中所有字母异位词 中等 同样比较字母频次，原题在长串的每个窗口中判断，本题只比较两条完整字符串。
49. 字母异位词分组 中等 同样以频次作为重排等价类，本题返回布尔值，原题据此对多个字符串分组。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/27938886
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！