剑指offer038按字典序打印字符串的所有排列

Problem:

输入一个字符串，按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc，则打印出由字符 a, b, c 所能排列出来的所有字符串 abc, acb, bac, bca, cab 和 cba。

Intuition:

对于无重复值的情况：固定第一个字符，递归取得首位后面的各种字符串组合；再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合；递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符换，然后继续处理子串。对于无重复值的情况：由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数， 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！

Solution:

public class CodingInterview_038 {


    public ArrayList<String> Permutation(String str){

        ArrayList<String> list = new ArrayList<String>();
        if(str!=null && str.length()>0){
            PermutationHelper(str.toCharArray(),0,list);
            //Collections.sort可以直接按字典序打印出字符串的排列，所以我们要做的实际上只是把字符串的全排列放到list里面去就行了
            Collections.sort(list);
        }
        return list;
    }

    //i表示用第i位与后面的字符交换
    private void PermutationHelper(char[] chars,int i,ArrayList<String> list){
        if(i == chars.length-1){
            list.add(String.valueOf(chars));
        }else{
            Set<Character> charSet = new HashSet<Character>();
            //用当前字符（下标为i的字符）放在第i位对应的字符串排列总数
            charSet.add(chars[i]);
            PermutationHelper(chars,i+1,list);
            //将第i个字符依次与后面的字符交换放在第i位对应第字符串第排列总数。
            for(int j=i+1;j<chars.length;++j){
                if(!charSet.contains(chars[j])){
                    charSet.add(chars[j]);
                    swap(chars,i,j);
                    PermutationHelper(chars,i+1,list);
                    swap(chars,j,i);
                }
            }
        }
    }


    private void swap(char[] cs,int i,int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}