剑指 Offer 38. 字符串的排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

输入输出

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

基本思路

  1. 终止条件：当x = len(c) - 1时 代表所有位已经固定 则将组合c转化为字符串并加入res并返回
  2. 地推参数：当前固定位x
  3. 递推工作：初始化一个Set 用于排除重复的字符；将第x位字符与i ∈ [x, len(c)]字符分别进行交换并递归
    1. 剪枝：若c[i]在Set中 代表其是重复字符因此剪枝
    2. 将c[i]加入Set 以便之后遇到重复字符时剪枝
    3. 固定字符：将字符c[i]和c[x]交换并固定c[i]为当前位字符
    4. 开启下层递归 调用dfs(x + 1)即开始固定第x+1个字符
    5. 还原交换：将字符c[i]和c[x]交换（还原之前的交换）
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
第一次：
i=0,x=0,dfs(x+1)
i=1,x=1,dfs(x+1)
i=2,x=2,dfs(x+1)
res.add({a,b,c})
第二次：
i=2,x=1,dfs(x+1) 交换 {a,c,b}
i=2,x=2,dfs(x+1)
res.add({a,c,b})
第三次：
i=1,x=0,dfs(x+1) 交换 {b,a,c}
i=1,x=1,dfs(x+1)
i=2,x=2,dfs(x+1)
res.add({b,a,c})
第四次：
i=2,x=1,dfs(x+1) 交换 {b,c,a}
i=2,x=2,dfs(x+1)
res.add({b,c,a})
第五次：
i=2,x=0,dfs(x+1) 交换 {c,b,a}
i=1,x=1,dfs(x+1)
i=2,x=2,dfs(x+1)
res.add({c,b,a})
第六次：
i=2,x=1,dfs(x+1) 交换 {c,a,b}
i=2,x=2,dfs(x+1)
res.add({c,a,b})

i=3,x=0跳出循环返回结果

java实现

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
30
31
32
class Solution {
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray(); //c = ['a', 'b', 'c']
        dfs(0);
        //res: "abc" -> "acb" -> "bac" -> "bca" -> "cab" -> "cba"
        return res.toArray(new String[res.size()]);
        // res = ["abc","acb","bac","bca","cab","cba"]
    }

    void swap(int a, int b){
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }

    void dfs(int x){
        if(x == c.length - 1){//x = 2
            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(i, x);
            dfs(x + 1);
            swap(i, x);
        }
    }
}