LeetCode 面试题 08.07. 无重复字符串的排列组合

2026-03-28 HGNULB 约 5 分钟

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

分类

题目描述

✅ 面试题 08.07. 无重复字符串的排列组合

题意分析

给定一个字符互不重复的字符串，返回全部排列。排列必须使用原字符串中的每个字符恰好一次；由于字符都不同，不需要考虑结果去重。

第 i 个位置可以从尚未使用的字符中任选一个。第 0 位有 n 种选法，第 1 位有 n-1 种，最终共有 $n!$ 个排列，任何正确算法至少要输出这么多结果。

题目字符按单字节英文字母处理，因此 Java 用 char[]、Go 用 []byte 都与题意一致。若放宽为任意 Unicode，Go 版需要改为 []rune，否则一个字符可能被拆成多个字节。

解法：逐位置选择未使用字符

核心思路

定义 dfs(i) 表示正在填写排列的第 i 个位置。t[0..i) 已经填好，vis[j] 表示原串下标 j 的字符是否已经被前缀使用。

在本层枚举所有 vis[j] == false 的字符：先标记使用并写入 t[i]，递归填写下一位，返回后撤销标记。循环不变量是：进入 dfs(i) 时，t 的前 i 位互不重复，且它们与 vis 中的 true 一一对应。

每个叶子对应一个原字符下标的排列；字符互不相同，所以不同下标排列必然生成不同字符串。枚举了每一层的所有未使用字符，也就不会漏掉任何排列。

解题步骤

准备长度为 n 的结果缓冲 t 和长度为 n 的使用标记 vis。

从 dfs(0) 开始；若 i == n，把完整缓冲转换成字符串并加入答案。

枚举原串的每个下标 j，跳过已经使用的字符。

选择 j：设 vis[j] = true、写入 t[i]，递归 dfs(i+1)。

返回后把 vis[j] 恢复为 false，让同层下一个候选可以使用该字符。

以 S = "abc" 为例。第一位选 a 后，第二位可选 b 或 c，得到 abc、acb；第一位再依次换成 b、c，分别得到 bac、bca 与 cab、cba，共 3! = 6 个结果。

代码实现

// i 表示当前填写位置，vis 表示原串字符是否已进入前缀。
class Solution {
    private char[] s;
    private char[] t;
    private boolean[] vis;
    private List<String> answer = new ArrayList<>();

    public String[] permutation(String S) {
        s = S.toCharArray();
        int n = s.length;
        vis = new boolean[n];
        t = new char[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]) {
                vis[j] = true;
                t[i] = s[j];
                dfs(i + 1);
                vis[j] = false;
            }
        }
    }
}

// i 表示当前填写位置，vis 表示原串字符是否已进入前缀。
func permutation(S string) (answer []string) {
    t := []byte(S)
    n := len(t)
    vis := make([]bool, n)
    var dfs func(int)
    dfs = func(i int) {
        if i >= n {
            answer = append(answer, string(t))
            return
        }
        for j := range S {
            if !vis[j] {
                vis[j] = true
                t[i] = S[j]
                dfs(i + 1)
                vis[j] = false
            }
        }
    }
    dfs(0)
    return
}

复杂度分析

时间复杂度：$O(n \cdot n!)$，共有 $n!$ 个排列，每个叶子构造长度为 n 的字符串。

空间复杂度：不计输出为 $O(n)$，包括递归栈、vis 和排列缓冲；输出本身为 $O(n \cdot n!)$。

关键点总结

排列与组合的区别在于位置有意义：每层都要从全部未使用字符中选择，而不是只从上次下标之后选。

vis 管的是“原串下标是否使用”，i 管的是“答案写到哪一位”，两个维度不要混用。

面试追问若要求原地写法，可把字符数组的第 i 位与后缀每一位交换，递归后换回；同样是 $O(n \cdot n!)$。

一旦输入允许重复字符，当前算法会生成重复结果，必须切换到排序 + 同层去重，对应下一题 08.08。

易错点总结

递归返回后忘记清除 vis[j]：S = "ab" 生成第一个结果后，其它分支再也无法使用被锁住的字符，答案缺失。

每层只从 i 之后的下标选择：这会退化成组合逻辑，"abc" 永远生成不了以 c 开头的排列。

到 i == n-1 就收集：最后一位尚未写入，结果包含旧值或空字符；应在 i == n 时收集。

Go 面对 Unicode 仍按字节遍历：中文字符会被拆开；若题目不再限定英文字母，应使用 rune。

相似题目

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