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

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

题目描述

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

image-20260929012105165

题意分析

返回由原字符串全部字符组成的所有排列，每个字符恰好使用一次。输入字符互不重复，因此不同的字符位置安排就对应不同答案，不需要额外去重。

排列的每个位置都有意义：第一位可以从全部 n 个字符中选，第二位从剩余 n - 1 个中选，依次下去，共有 n! 个结果。本文按题中的英文字母使用 Java 字符数组和 Go 字节数组。

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

核心思路

[!blue]

定义 dfs(i) 为填写排列的第 i 个位置。缓冲区 t[0..i) 是已经选好的前缀，vis[j] 表示原字符串下标 j 的字符是否已经出现在这个前缀里。i 是输出位置，j 是输入字符位置，二者用途不同。

本层枚举全部尚未使用的 j，将它标记为已使用，并把字符写到 t[i]，然后递归填写下一位。进入下一层时，前缀恰好多了一个未重复的字符，vis 也与前缀使用的下标保持一致。

递归返回后撤销 vis[j]，让其他分支能重新选择这个字符。t[i] 不必清空，因为本层下一个选择会覆盖它，之后的每一位也都会在抵达叶子前重新写入。

当 i == n 时，前缀已经使用全部字符，转换为字符串保存。每个排列都能唯一确定各层选择的下标，而每层又枚举了所有未用下标，因此既不漏解也不重复。保存出的字符串独立于后续会继续改写的字符缓冲。

解题步骤

  1. 准备长度为 n 的字符缓冲 t 和使用标记 vis，从 dfs(0) 开始。
  2. 若 i == n，将完整缓冲转换为字符串加入答案，并返回。
  3. 枚举原串所有下标，跳过 vis[j] == true 的字符。
  4. 令 vis[j] = true，写入 t[i]，递归到 i + 1。
  5. 返回后令 vis[j] = false，继续本层的其他选择。

代码实现

// 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!)$。

关键点总结

[!green]

  • 每层决定一个输出位置，候选是所有未使用的输入下标，不能只选上次下标之后的字符。
  • vis 与已填前缀一一对应，保证每个字符在一个排列里恰好使用一次。
  • 输入字符互不相同，枚举下标排列本身就能保证答案唯一。

易错点总结

[!yellow]

  • 递归后忘记撤销使用标记，会把当前分支的选择错误地保留到其他分支。
  • 用输出位置 i 限制输入下标范围，会漏掉需要把靠后字符放到前面的排列。
  • 在 i == n - 1 时就收集，最后一位还未填写，应等所有位置写完。
  • 字符缓冲在整个搜索中复用，叶子应保存转换得到的字符串，不能保存之后仍会改动的同一缓冲。

相似题目

题目 难度 关联与区别
面试题 08.08. 有重复字符串的排列组合 中等 输入允许重复字符后，需要排序并剪掉同层等价选择。
31. 下一个排列 中等 同样枚举排列的相邻顺序，原题只求一个后继，本题一次输出所有排列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/60458727
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！