• 示例工程
• 教程

本文以 doocs/leetcode 开源仓库中的 lcci/01.02.Check Permutation/README_EN.md 为核心，系统讲解《程序员面试金典》面试题 01.02「判定是否互为字符重排」的完整解法：哈希计数法（数组/哈希表）与排序法，并给出 Python、Java、C++、Go、TypeScript、Rust、JavaScript、Swift 八种语言的仓库级实现，以及时间/空间复杂度对比与边界情况讨论。读完本文，你将掌握"两个字符串互为排列"问题的判定原理、两种解法的取舍依据，以及如何在多语言工程中落地这套标准解法。

题目描述与约束

原题（英文题面 / 中文题面）：

Given two strings, write a method to decide if one is a permutation of the other.

给定两个字符串s1和s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例：

约束条件（Note）：

• 0 <= len(s1) <= 100
• 0 <= len(s2) <= 100

关键约束提示：本题测试用例中的所有字符串仅包含小写字母，这直接决定了方法一可以使用长度为26的定长数组充当哈希表，将计数空间压缩到常量级。

核心思路：互为排列的本质

两字符串互为排列（permutation），当且仅当两者的字符多重集合（multiset）完全相同——即每个字符的出现次数逐一相等。

据此可以立刻得出两条推论：

1. 长度不等必为 false：若len(s1) != len(s2)，二者的字符总数不同，直接返回false，无需任何统计。
2. 枚举全排列是错误方向：若枚举s1的全部排列再与s2逐一比较，代价为阶乘级，远超题目规模所需。正确方向是"核对字符频次"。

围绕"核对频次"，业界与本题仓库给出了两条主线解法：

• 方法一：哈希计数（数组 / 哈希表）——时间最优，O(n)；
• 方法二：排序比较——实现最简，O(n log n)，且不依赖字符集规模假设。

下面分别展开，每种方法均给出仓库中Solution.*与Solution2.*的真实源码实现。

方法一：哈希计数（数组或哈希表）

算法流程

1. 比较两字符串长度，不等则直接返回false；
2. 用一个数组或哈希表统计s1中每个字符的出现次数；
3. 遍历s2，每遇到一个字符就将其对应计数减一；
4. 若某字符减一后的计数小于0，说明该字符在s2中出现的次数多于在s1中的次数，两串频次不一致，返回false；
5. 遍历完s2仍无异常，返回true。

为什么"减一后小于 0"即判负：两串长度相同，若s2中某字符出现次数超过s1，必然会有另一字符在s2中出现次数少于s1，最终计数数组不可能全部归零，因此在扫描途中一旦出现负数即可提前终止。

计数容器的选择：

Python3 实现

仓库文件：Solution.py

class Solution: def CheckPermutation(self, s1: str, s2: str) -> bool: return Counter(s1) == Counter(s2)

Python 直接利用collections.Counter构造两个字符计数多重集合，比较相等即判定结果。注意：Counter相等比较对缺失键与零值计数视为等价（例如Counter({'a': 0}) == Counter()为True），恰好契合"频次一致"的语义。

Java 实现

仓库文件：Solution.java

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; } }

char参与算术运算时自动提升为int，c - 'a'将a~z映射到下标0~25。

C++ 实现

仓库文件：Solution.cpp

class Solution { public: bool CheckPermutation(string s1, string s2) { if (s1.size() != s2.size()) { return false; } int cnt[26]{}; for (char c : s1) { ++cnt[c - 'a']; } for (char c : s2) { if (--cnt[c - 'a'] < 0) { return false; } } return true; } };

int cnt[26]{}值初始化将全部元素置零。

Go 实现

仓库文件：Solution.go

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 }

注意 Go 中for _, c := range遍历字符串时c为rune，但本题仅含小写字母，c-'a'的差值恒为非负整数，可直接作下标。

TypeScript 实现

仓库文件：Solution.ts

function CheckPermutation(s1: string, s2: string): boolean { if (s1.length !== s2.length) { return false; } const cnt: Record<string, number> = {}; for (const c of s1) { cnt[c] = (cnt[c] || 0) + 1; } for (const c of s2) { if (!cnt[c]) { return false; } cnt[c]--; } return true; }

TS/JS 无原生定长数组计数习惯，采用Record<string, number>哈希对象：(cnt[c] || 0) + 1处理首次出现的键；扫描s2时!cnt[c]捕获计数为0或缺失的情况。

Rust 实现

仓库文件：Solution.rs

impl Solution { pub fn check_permutation(s1: String, s2: String) -> bool { if s1.len() != s2.len() { return false; } let mut cnt = vec![0; 26]; for c in s1.chars() { cnt[(c as usize - 'a' as usize)] += 1; } for c in s2.chars() { let index = c as usize - 'a' as usize; if cnt[index] == 0 { return false; } cnt[index] -= 1; } true } }

Rust 中char先转usize再作下标；扫描s2时用cnt[index] == 0代替负数判断（vec![0; 26]内为无符号计数语义），同样能提前判负。

JavaScript 实现

仓库文件：Solution.js

/** * @param {string} s1 * @param {string} s2 * @return {boolean} */ var CheckPermutation = function (s1, s2) { if (s1.length !== s2.length) { return false; } const cnt = {}; for (const c of s1) { cnt[c] = (cnt[c] || 0) + 1; } for (const c of s2) { if (!cnt[c]) { return false; } cnt[c]--; } return true; };

Swift 实现

仓库文件：Solution.swift

class Solution { func CheckPermutation(_ s1: String, _ s2: String) -> Bool { if s1.count != s2.count { return false } var cnt = Int for char in s1 { cnt[Int(char.asciiValue! - Character("a").asciiValue!)] += 1 } for char in s2 { let index = Int(char.asciiValue! - Character("a").asciiValue!) if cnt[index] == 0 { return false } cnt[index] -= 1 } return true } }

Swift 通过asciiValue（UInt8）相减得到0~25的下标。

复杂度分析（方法一）

• 时间复杂度：O(n)，其中n为字符串长度（两串长度相等时）；两次线性扫描，一次统计、一次核对。
• 空间复杂度：O(C)，C为字符集大小。本题仅含小写字母，C = 26，因此数组实现的空间为常量O(1)；若用哈希表，则空间随实际出现的不同字符数增长，最坏仍为O(C)。

方法二：排序

算法流程

1. 将s1与s2各自按字典序（lexicographical order）排序；
2. 比较排序后的两串是否相等：相等即互为排列，否则不是。

原理：排序是多重集合的规范化（canonical form）——同一多重集合的任意排列排序后得到相同序列，不同多重集合排序后必不相同。与计数法相比，排序法不假设字符集规模，实现代码更短，代价是时间升至O(n log n)。

Python3 实现

仓库文件：Solution2.py

class Solution: def CheckPermutation(self, s1: str, s2: str) -> bool: return sorted(s1) == sorted(s2)

Java 实现

仓库文件：Solution2.java

class Solution { public boolean CheckPermutation(String s1, String s2) { char[] cs1 = s1.toCharArray(); char[] cs2 = s2.toCharArray(); Arrays.sort(cs1); Arrays.sort(cs2); return Arrays.equals(cs1, cs2); } }

注意使用Arrays.equals比较字符数组内容（引用==比较的是地址）。

C++ 实现

仓库文件：Solution2.cpp

class Solution { public: bool CheckPermutation(string s1, string s2) { ranges::sort(s1); ranges::sort(s2); return s1 == s2; } };

C++ 版本采用 C++20 的std::ranges::sort就地排序后直接比较字符串。

Go 实现

仓库文件：Solution2.go

func CheckPermutation(s1 string, s2 string) bool { cs1, cs2 := []byte(s1), []byte(s2) sort.Slice(cs1, func(i, j int) bool { return cs1[i] < cs1[j] }) sort.Slice(cs2, func(i, j int) bool { return cs2[i] < cs2[j] }) return string(cs1) == string(cs2) }

Go 将字符串转[]byte排序后转回string比较（本题仅 ASCII 小写字母，[]byte安全）。

TypeScript 实现

仓库文件：Solution2.ts

function CheckPermutation(s1: string, s2: string): boolean { return [...s1].sort().join('') === [...s2].sort().join(''); }

Rust 实现

仓库文件：Solution2.rs

impl Solution { pub fn check_permutation(s1: String, s2: String) -> bool { let mut s1: Vec<char> = s1.chars().collect(); let mut s2: Vec<char> = s2.chars().collect(); s1.sort(); s2.sort(); s1 == s2 } }

JavaScript 实现

仓库文件：Solution2.js

/** * @param {string} s1 * @param {string} s2 * @return {boolean} */ var CheckPermutation = function (s1, s2) { return [...s1].sort().join('') === [...s2].sort().join(''); };

Swift 实现

仓库文件：Solution2.swift

class Solution { func CheckPermutation(_ s1: String, _ s2: String) -> Bool { let s1 = s1.sorted() let s2 = s2.sorted() return s1 == s2 } }

复杂度分析（方法二）

• 时间复杂度：O(n × log n)，由两次排序主导，n为字符串长度。
• 空间复杂度：O(n)，取决于所用排序实现（如归并排序的辅助空间）；部分语言对短数组采用就地插入排序，但最坏仍视为O(n)。

两种方法对比与选型

实践建议：面试场景优先给出方法一并说明26数组的由来（题目仅含小写字母）；随后可追问"若字符集包含 Unicode 如何处理"，此时切换哈希表版或排序法即可覆盖。若两串长度不等，两种方法都可先做长度短路（排序法虽然代码里未显式判断，但排序后比较仍正确，只是略多开销）。

仓库源码结构说明

在 doocs/leetcode 仓库中，本题目录 lcci/01.02.Check Permutation 下并存两套独立源码文件：

• Solution.*（8 个文件）：方法一哈希计数实现，对应 README 的Solution 1；
• Solution2.*（8 个文件）：方法二排序实现，对应 README 的Solution 2。

涉及的编程语言包括 Python3、Java、C++、Go、TypeScript、Rust、JavaScript、Swift，且各语言的独立文件与 README_EN.md 中展示的代码完全一致，可直接对照阅读或本地运行验证。该目录隶属于仓库的 lcci 题解专区（《程序员面试金典》第 6 版），题目元数据（frontend_id、标题、难度等）统一收录于 lcci/lcci.json，本题difficulty标记为Easy（简单）。

边界情况与扩展讨论

边界用例验证：

扩展点 1——字符集放大：若输入扩展为任意 ASCII 可打印字符（95 个）或 Unicode，可把定长数组改为int[128]、int[256]，或直接换用哈希表（各语言Solution.*的哈希表版本思路通用）。

扩展点 2——内存受限变体：若要求O(1)额外空间且字符集极大，可在长度相等前提下先排序后比较（原地排序），但时间升为O(n log n)——这正是方法二的适用场景。

扩展点 3——相关题目迁移：该"频次核对"模板在同类题目中复用度高，例如统计异位词（anagram）分组、判断字符串是否可通过重排变为回文等，核心都是先构建字符多重集合再做一次核对。

总结

面试题 01.02「判定是否互为字符重排」的核心结论可浓缩为一句：互为排列 ⇔ 字符多重集合相同。工程上两条路线——O(n)的哈希计数与O(n log n)的排序比较——覆盖了"字符集已知求最快"与"实现最简求通用"两类诉求。doocs/leetcode 仓库为该题提供了 8 种语言的完整双解法源码（Solution.* 与 Solution2.*），是读者验证实现、对比语言差异的直接素材，建议结合 README_EN.md 逐一对照阅读。

• 示例工程
• 教程