剑指offer38

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

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

1. String.valueOf(char[] data):将char[]数组转换成String
2. list.toArray(new String[list.size()])把list容器转化为指定类型的数组
3. Set容器(不容许有重复元素的集合):HashSet<String> site=new HashSet<>()
4. Set方法：add(),remove(String),contains(String)

dfs+回溯。用一个全局的visit数组来记录下使用过的字符 ，回溯前再置为0。 一开始去重用的是!list.contains(String),后面发现超时了。然后又改成HashSet容器来装字符串数组，居然能AC，可能这就是HashSet的魅力吧。减少时间的关键在于剪支，同一个位置(意味着同一个dfs内的循环)如果是先前使用过的字符则可直接continue，所以在每一个dfs都要开辟一个HashSet来记录当前位置使用过的字符。剪枝过后就不需要去重。

class Solution {
    int[] visit=new int[8]; 
    HashSet<String> list=new HashSet<>();
    public String[] permutation(String s){
            char[] temp=new char[s.length()];
            dfs(s,temp,0);                     
            return list.toArray(new String[list.size()]);
    }
    public void dfs(String s,char[] temp,int charindex)
    {
        if(s.length()==charindex)
        {     
            list.add(new String(temp,0,s.length()));              
            return;
        }
        HashSet<Character> v=new HashSet<>(); //真正的剪枝
        for(int i=0;i<s.length();i++)
        {
            if(visit[i]==0&&!v.contains(s.charAt(i)))
            {
                visit[i]=1;
                v.add(s.charAt(i));
                temp[charindex]=s.charAt(i);
                dfs(s,temp,charindex+1);               
                visit[i]=0;
                if(charindex==s.length()-1) //假的剪枝
                return;
            }                       
        }
    }
}