LeetCode 面试题 08.08. 有重复字符串的排列组合

2026-03-28 HGNULB 约 5 分钟

文章信息 3 个分类 2 个标签

分类

题目描述

✅ 面试题 08.08. 有重复字符串的排列组合

题意分析

与 08.07 相同，要使用全部字符生成排列；区别是输入可能包含重复字符，返回结果中不能出现重复字符串。

若仍把相同字符的不同下标当成不同选择，"aab" 中两个 a 互换会生成完全相同的排列，每个合法结果都会被重复多次。去重必须发生在搜索过程中，而不是生成全部 $n!$ 个结果后再塞进集合，否则浪费的分支已经走完。

排序让相同字符相邻，才有可能用一个局部条件跳过等价分支。设字符总数为 n、各字符频次为 $c_1,c_2,\ldots$，不同排列数是 $U=n!/\prod c_i!$。

解法：排序 + 同层去重回溯

核心思路

先排序字符，再沿用“逐位置选择未使用字符”的回溯。关键剪枝是：当 s[j] == s[j-1] 且前一个相同字符在当前层还没有被使用时，跳过 s[j]。

为什么条件是 !vis[j-1]？同一层里，两个相同字符作为当前位置的选择完全等价，我们约定只允许它们按排序后的下标顺序被选：前一个还没进入当前前缀，就不允许后一个抢先作为本层选择。若前一个已经在更高层使用，后一个当然可以选，否则 "aa" 连第二个位置都填不满。

这个规则只剪掉同一搜索层的等价兄弟分支，不会剪掉不同位置需要使用多个相同字符的合法路径。排序 + vis 共同保证了这一点，二者缺一不可。

解题步骤

把字符串转为字符数组并排序，使相同字符相邻。

准备排列缓冲 t、使用标记 vis，从位置 0 开始回溯。

枚举字符下标 j：已使用则跳过；若与前一字符相同且前一字符尚未使用，也跳过。

选择字符、递归下一位置，返回后撤销 vis[j]。

填满 n 个位置后，把缓冲转换为字符串加入答案。

以 S = "aab" 为例。第一层允许选下标 0 的 a，跳过下标 1 的 a，还可选 b。以第一个 a 开头时，下一层前一个 a 已使用，所以第二个 a 可以被选，得到 aab、aba；以 b 开头时再依次使用两个 a，得到 baa。最终恰好三个不同排列。

代码实现

// 相同字符必须按下标顺序进入当前前缀，剪掉同层等价分支。
class Solution {
    private char[] s;
    private char[] t;
    private boolean[] vis;
    private List<String> answer = new ArrayList<>();

    public String[] permutation(String S) {
        int n = S.length();
        s = S.toCharArray();
        Arrays.sort(s);
        t = new char[n];
        vis = new boolean[n];
        dfs(0);
        return answer.toArray(new String[0]);
    }

    private void dfs(int i) {
        if (i >= s.length) {
            answer.add(new String(t));
            return;
        }
        for (int j = 0; j < s.length; ++j) {
            if (!vis[j] && (j == 0 || s[j] != s[j - 1] || vis[j - 1])) {
                vis[j] = true;
                t[i] = s[j];
                dfs(i + 1);
                vis[j] = false;
            }
        }
    }
}

// 相同字符必须按下标顺序进入当前前缀，剪掉同层等价分支。
func permutation(S string) (answer []string) {
    s := []byte(S)
    sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
    t := slices.Clone(s)
    vis := make([]bool, len(s))
    var dfs func(int)
    dfs = func(i int) {
        if i >= len(s) {
            answer = append(answer, string(t))
            return
        }
        for j := range s {
            if !vis[j] && (j == 0 || s[j] != s[j-1] || vis[j-1]) {
                vis[j] = true
                t[i] = s[j]
                dfs(i + 1)
                vis[j] = false
            }
        }
    }
    dfs(0)
    return
}

复杂度分析

时间复杂度：排序为 $O(n \log n)$；生成并复制 U 个不同排列为 $O(n \cdot U)$，总体 $O(n \log n + nU)$，其中 $U=n!/\prod c_i!$。

空间复杂度：不计输出为 $O(n)$，用于递归栈、使用标记和排列缓冲；输出为 $O(nU)$。

关键点总结

去重对象是同一层的选择，不是整条路径中的字符；路径里本来就可能合法地使用多个相同字符。

标准剪枝 s[j] == s[j-1] && !vis[j-1] 的含义是“相同字符按下标顺序入选”，而不是需要机械背诵的公式。

面试时应先写无重复排列，再说明重复输入会在哪里产生等价兄弟分支，最后加排序与一行剪枝，演进最自然。

用集合事后去重虽然容易想到，但仍遍历 $n!$ 个叶子，并额外保存哈希键，不是推荐主解。

易错点总结

不排序就比较相邻字符："aba" 的两个 a 不相邻，剪枝看不见它们，仍会产生重复排列。

剪枝条件写成 vis[j-1]：当前缀已经使用前一个相同字符时反而禁止后一个，"aa" 无法填满两个位置。

只写 s[j] == s[j-1] 就无条件跳过：同样会把第二个 a 永久禁用，丢失所有需要多个 a 的合法排列。

忘记撤销 vis[j]：完成一个分支后字符保持占用，后续排列不完整。

相似题目

题目	难度	考察点
46. 全排列	中等	排列回溯
47. 全排列 II	中等	排列回溯
60. 排列序列	困难	排列回溯
784. 字母大小写全排列	中等	排列回溯
LCR 083. 全排列	中等	排列回溯
LCR 084. 全排列 II	中等	排列回溯
剑指 Offer 38. 字符串的排列	中等	排列回溯
面试题 08.07. 无重复字符串的排列组合	中等	排列回溯