剑指offer 38：字符串的排列

链接

题目：

思路：

思路和全排列 II 相同！ 只是 数字换成了 char 字符；

1. 可能有重复元素，就要先排序！ char也是可以通过 Arrays.sort() 排序的 ！
2. dfs： path使用Stringbuffer来装，当 Stringbuffer的length 到达数组长度就添加到 r；
   由于StringBuffer没有contains() 方法，使用onpath[] 数组记录元素是否被遍历过；
   为避免重复，添加判断：if(i>0 && c[i]==c[i-1] && !onpath[i-1]){ continue; }
3. 结果用List< String > 来装，最后转换为 String数组；

注意：

1. StringBuffer没有size() , 但是有 length()
   

2. StringBuffer没有 removeLast()，但是有deleteCharAt() 用来删除指定位置的字符
   

3. 多种基本数据类型都能通过append追加到Stringbuffer
   

4. 结果数组String[] r 的元素个数不是 输入字符的个数！ 而是list中的结果种数 list.size()！

Java实现：

class Solution {
    List<String> r=new ArrayList<>();
    StringBuffer path=new StringBuffer();
    boolean[] onpath;
    public String[] permutation(String s) {
        char[] c=s.toCharArray();
        onpath=new boolean[s.length()];
        // 重复就要先排序！
        // char也可以排序！
        Arrays.sort(c);
        dfs(c);
        int n=r.size();
        String[] res=new String[n];
        for(int i=0;i<n;i++){
            res[i]=r.get(i);
        }
        return res;
    }

    void dfs(char[] c){
        // 到达个数就添加到 r
        if(path.length()==c.length){
            r.add(path.toString());
            return;
        }
        for(int i=0;i<c.length;i++){
            // 选择
            if(onpath[i]){
                continue;
            }
            if(i>0 && c[i]==c[i-1] && !onpath[i-1]){
                continue;
            }
            onpath[i]=true;
            path.append(c[i]);
            // 递归
            dfs(c);
            // 撤销
            path.deleteCharAt(path.length()-1);
            onpath[i]=false;
        }
    }
}
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
33
34
35
36
37
38
39
40
41
42
43