LeetCode 剑指 Offer 38. 字符串的排列
目录
题目描述
题意分析
给一个字符串
s，返回它所有字符组成的所有排列，结果以字符串数组返回，顺序不限。要什么：把
s的每一个字符都用上、且每个字符恰好用一次，穷举出所有可能的先后顺序。这里有个必须先说清楚的点：
s里可能包含重复字符，结果不能有重复的排列。例如s = "aab"，两个a在题目眼里是不可区分的，正确答案只有"aab"、"aba"、"baa"三个，而不是把两个a当成不同个体得到的 6 个。这条要求把题目从「模板全排列」拉高到了「带去重的全排列」，也是本题真正的考点。约束信号：
1 <= s.length <= 8。8! = 40320，答案本身就是指数级规模，所以不存在多项式解法，出题人接受的就是穷举，只是要求穷举得不重复。同时 8 这个上限也说明可以放心用递归，栈深最多 8 层，不必考虑改写成迭代。边界要想到：长度为 1 时返回单元素数组；全部字符相同时（比如
"aaa"）结果只有 1 个；s里的重复可能不止一组（比如"aabb"）；返回类型是String[]而不是List<String>，最后要做一次转换。
解法：排序 + 回溯去重
核心思路
全排列必须枚举搜索树，但不能等生成后再用集合去重：重复字符越多，无效分支越多。先排序，让相同字符相邻，再用
used标记路径上已选择的下标。重复只会发生在同一层选择相同字符时。剪枝条件
idx > 0 && chars[idx] == chars[idx - 1] && !used[idx - 1]
表示：左侧同值字符还未进入当前路径时，不允许先选当前字符。这样为每组相同字符固定了从左到右的使用顺序。搜索不变量是：当前路径中的下标互不重复，且同值字符按下标递增使用。因此每个叶子都是合法排列，而任意一个不同的排列又都有唯一的选择路径，既不重也不漏。
解题步骤
- 将字符排序，创建
used、路径缓冲和结果列表。- 每层枚举所有下标：已使用的下标跳过；若当前字符与前一个相同且前一个未使用，也跳过。
- 选择字符后递归，返回时同时撤销路径和
used状态。- 路径长度等于
n时收集答案。以
"aab"为例：根节点可以选第一个a或b，但不能先选第二个a；因此只生成aab、aba、baa。注意used[idx - 1] == true时第二个a可以选，否则连两个a都无法同时进入排列。
代码实现
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public String[] permutation(String s) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
boolean[] used = new boolean[chars.length];
List<String> res = new ArrayList<>();
StringBuilder path = new StringBuilder();
dfs(chars, used, path, res);
return res.toArray(new String[0]);
}
private void dfs(char[] chars, boolean[] used, StringBuilder path, List<String> res) {
if (path.length() == chars.length) {
res.add(path.toString());
return;
}
for (int idx = 0; idx < chars.length; idx++) {
if (used[idx]) {
continue;
}
// 相同字符只允许按从左到右的顺序进入同一层分支。
if (idx > 0 && chars[idx] == chars[idx - 1] && !used[idx - 1]) {
continue;
}
used[idx] = true;
path.append(chars[idx]);
dfs(chars, used, path, res);
path.deleteCharAt(path.length() - 1);
used[idx] = false;
}
}
}
import "sort"
func permutation(s string) []string {
chars := []byte(s)
sort.Slice(chars, func(i int, j int) bool {
return chars[i] < chars[j]
})
used := make([]bool, len(chars))
path := make([]byte, 0, len(chars))
res := make([]string, 0)
var dfs func()
dfs = func() {
if len(path) == len(chars) {
res = append(res, string(path))
return
}
for idx := 0; idx < len(chars); idx++ {
if used[idx] {
continue
}
// 相同字符只允许按从左到右的顺序进入同一层分支。
if idx > 0 && chars[idx] == chars[idx-1] && !used[idx-1] {
continue
}
used[idx] = true
path = append(path, chars[idx])
dfs()
path = path[:len(path)-1]
used[idx] = false
}
}
dfs()
return res
}
复杂度分析
- 时间复杂度：最坏为 $O(n \cdot n!)$，共有
n!个结果，每个结果需复制n个字符。- 空间复杂度：$O(n)$（不计结果），来自递归栈、路径和
used；结果最坏占 $O(n \cdot n!)$。
关键点总结
used防止同一下标重复使用；排序剪枝防止同层选择重复值，职责不同。!used[idx - 1]表示前一个同值字符不在路径中，此时选择当前字符会生成重复子树。- 选择与撤销必须成对，避免状态污染兄弟分支。
- 若不能排序，可以改为每层使用一个集合记录已选字符，但会增加空间和代码。
易错点总结
- 未排序就使用相邻剪枝，会漏掉不相邻的重复字符，如
"aba"。- 剪枝条件缺少
!used[idx - 1]，会把路径中本应允许的第二个相同字符也剪掉。- 回溯后漏恢复
used或路径，会污染后续分支。- Go 若直接保存可变
[]byte路径会共享底层数组；转成string(path)再收集。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 46. 全排列 | 中等 | 元素互异的排列枚举模板 |
| 47. 全排列 II | 中等 | 排序后同层剪枝去重 |
| 60. 排列序列 | 困难 | 不枚举全部排列直接定位第 k 个 |
| 784. 字母大小写全排列 | 中等 | 每个字母大小写二选一的分支枚举 |
| LCR 083. 全排列 | 中等 | 排列回溯模板的 LCR 版题号 |
| LCR 084. 全排列 II | 中等 | 含重复元素排列去重的 LCR 版题号 |
| 面试题 08.07. 无重复字符串的排列组合 | 中等 | 字符集无重复时的排列输出 |
| 面试题 08.08. 有重复字符串的排列组合 | 中等 | 字符集有重复时的排列输出 |