【全排列】38题-字符串的排列_输入一个长度为 n 由大小写字母组成的字符串,打印出该字符串中字符的所有排列,例

1 题目描述

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例：

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
1
2

限制：

1 <= s 的长度 <= 8
1

2 解题思路

排列方案数量： 对于一个长度为n的字符串（假设字符不重复），其排列共有$n\times (n-1)\times (n-2)...\times 2\times 1$种方案。

排列方案的生成方法： 根据字符串排列的特点，考虑深度优先搜索所有排列方案。即通过字符交换，先固定第1位字符（n种情况）、再固定第2位字符（n-1种情况）、…、最后固定第n位字符（1种情况）。

重复方案与剪枝： 当字符串存在重复字符时，排列方案也存在重复方案。为排除重复方案，需在固定某位字符时，保证“每种字符只在此位固定一次”，即遇到重复字符时不交换，直接跳过。从DFS角度看，此操作称为“剪枝”。

递归解析：

• 终止条件：当x=len( c ) - 1时，代表所有位已固定（最后一位只有1种情况），则将当前组合c转化为字符串并加入res，并返回；
• 递推参数：当前固定位x；
• 递推工作：初始化一个Set，用于排除重复的字符；将第x位字符与$i\in [x,len(c)]$字符分别交换，并进入下层递归；
  • 剪枝：若c[i]在Set中，代表其是重复的字符，因此“剪枝”；
  • 将c[i]加入Set，以使之后遇到重复字符时剪枝；
  • 固定字符：将字符c[i]和c[x]交换，即固定c[i]为当前位字符；
  • 开启下层递归：调用dfs(x+1)，即开始固定第x+1个字符；
  • 还原交换：将字符c[i]和c[x]交换（还原之前的交换）；

class Solution {
    LinkedList<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();    
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    private void dfs(int x) {
        if (x == c.length - 1) {
            res.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = x;i < c.length;i++) {
            if (set.contains(c[i])) continue; 
            set.add(c[i]);
            swap(x,i);
            dfs(x + 1);
            swap(x,i);
        }
    }

    private void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

复杂度分析：

• 时间复杂度O(N!)：N为字符串 s 的长度；时间复杂度和字符串排列的方案数成线性关系，方案数为$N\times (N-1)\times (N-2)\dots \times 2\times 1$，因此复杂度为O(N!)。
• 空间复杂度 $O(N^2)$：全排列的递归深度为N，系统累计使用栈空间大小为O(N)；递归中辅助 Set 累计存储的字符数量最多为$N+(N-1)+...+2+1=(N+1)N/2$，即占用$O(N^2)$的额外空间。