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

约 5 分钟
文章信息 3 个分类 2 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
字符串 回溯

题目描述

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

image-20260929012111308

题意分析

返回英文字母字符串的所有不同排列，每个结果都要使用全部字符，并保留重复字符的原有数量。不同下标上的相同字符不能被当成不同答案，去重也不能把这些字符的副本删掉。

解法：排序并限制重复字符的选择顺序

核心思路

[!blue]

仍然逐位置选择尚未使用的字符：dfs(i) 填写输出位置 i，t[0..i) 是已填前缀，vis[j] 记录输入下标 j 是否已被前缀使用。但相同字符的下标互换会生成相同字符串，需要为这些副本规定唯一的选择顺序。

先排序，使相同字符相邻。枚举 j 时，如果它与前一个字符相同，并且前一个下标还没有使用，就跳过 j。因为当前这一位选择较早的那份相同字符即可，选择较晚的副本会形成等价分支。

若前一个相同字符已经在前缀中，当前副本就可以使用，不能一概跳过重复字符。代码中的条件 j == 0 || s[j] != s[j - 1] || vis[j - 1]，正是要求每种字符优先使用当前最靠前的未用副本。

这样相同字符沿一条完整路径总按下标顺序进入排列。任意合法的字符排列，都可以把同字符的第几次出现分配给排序后第几份副本，恰好得到一条保留的路径；其他仅交换相同副本身份的路径被剪掉。因此既保留全部不同排列，又不产生重复答案。

选择后标记并填写当前位，递归返回后撤销标记。所有位置填满时把缓冲转换成独立字符串保存；下一分支会覆盖字符位置，不需要把缓冲逐项清空。

解题步骤

  1. 将输入转为字符数组并排序，准备等长缓冲和全为未使用的标记。
  2. 从第 0 个输出位置开始，每层枚举全部输入下标。
  3. 跳过已经使用的下标，以及“与前一字符相同、前一副本尚未使用”的下标。
  4. 对允许的候选，标记使用、填入当前位置、递归下一位，返回后撤销标记。
  5. 填满全部位置时保存字符串，直到所有允许的分支完成。

代码实现

// 相同字符必须按下标顺序进入当前前缀，剪掉同层等价分支。
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;
            }
        }
    }
}

import (
    "slices"
    "sort"
)

// 相同字符必须按下标顺序进入当前前缀，剪掉同层等价分支。
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
}

复杂度分析

  • 时间复杂度：设长度为 $n$，不同排列数为 $U$。排序为 $O(n\log n)$；每层不同前缀数不超过 $U$，总计最多 $O(nU)$ 个搜索节点，而当前实现每个非叶节点都扫描全部 $n$ 个下标，故可给出 $O(n\log n+n^2U)$ 的上界。不能直接写成 $O(nU)$：字符全相同时虽然只有一个结果，仍需在 $n$ 层中各扫描 $n$ 个候选。
  • 空间复杂度：不计返回结果为 $O(n)$，用于字符缓冲、标记和递归栈；输出占 $O(nU)$。

关键点总结

[!green]

  • 排序将相同副本放在一起，使用顺序限制才真正完成去重。
  • 前一相同副本未使用时跳过当前副本；前一副本已进入路径时允许继续使用。
  • 每个不同字符排列保留一种规范的副本下标安排，去重不损失字符重数。

易错点总结

[!yellow]

  • 用集合去掉重复字符，会改变输入重数，生成的就不是原字符串排列。
  • 把相同字符一律跳过，会使需要多份相同字符的排列无法填满。
  • 将“前一副本未使用”的条件写反，会改变这套按下标顺序选择的去重规则。
  • 递归返回后不撤销 vis，会把本分支的选择错误地限制到后续分支。
  • 仅仅排序而不检查副本使用状态，仍会枚举出相同的字符串。

相似题目

题目 难度 关联与区别
面试题 08.07. 无重复字符串的排列组合 中等 基础回溯相同，本题新增相同字符副本的选择顺序限制。
90. 子集 II 中等 同样按层剪掉重复选择，但子集题每层只枚举后续下标，排列题枚举所有未使用下标。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/53200343
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！