剑指 Offer 38. 字符串的排列

大致思路为：先由字符串生成一个字符数组，对数组中的字符顺序进行变换，当得到新的排序时就将该数组生成一个字符串，加入到结果集合中。

字符顺序的变换规则为：深度优先遍历，对数组的每一位进行固定，第一位能固定的值有n个。通过for循环将每一位都固定在第一位一次。当重复时跳过该轮固定。固定的方法为将该位置的字符与深度遍历第x层的x为进行交换，交换之后继续深度优先遍历第x+1层。当该次固定的深度优先遍历完成后，将原来发生的交换复原，然后进行该层的下一次固定。最终得到所有可能。

class Solution {
    List<String> res = new ArrayList<>();
    char[] c; 
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    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);
        }
    }
    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