41_字符串的排列

要求：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路：使用全排列算法
方法见19_全排列递归算法

public class L39_permutation {
    // 全排列算法
    static ArrayList<String> res = new ArrayList<>();
    static char[] c;
    public static String[] permutation(String str) {
        // 将字符串转化为数组
        c = str.toCharArray();
        int len = c.length;
        dfs(0,len);
        // 将ArrayList转化为字符数组，先把链表的每个值取出来，然后拼接到一起，隔着"，"，利用字符分割split("，")切分成数组
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<=res.size()-1;i++){
            sb.append(res.get(i)+",");
        }
        String[] val = sb.deleteCharAt(sb.length()-1).toString().split(",");
        return val;
    }
    //递归
    public static void dfs(int m, int len){
        HashSet<Character> set = new HashSet<>();
        if(m == len){
            res.add(String.copyValueOf(c));
        }else{
            for(int i=m; i<len;i++){
                // 如果有重复的字符，要剪掉,即相同的字母只固定一次
                if(set.contains(c[i])) continue; // 重复，因此剪枝
                set.add(c[i]);
                // 交换，固定第一位
                char temp = c[m];
                c[m] = c[i];
                c[i] = temp;
                // 递归
                dfs(m+1, len);
                // 交换回去
                temp = c[m];
                c[m] = c[i];
                c[i] = temp;
            }
        }
    }

    public static void main(String[] args) {
        String[] str = permutation("abbb");
        int len = str.length;
        for(int i=0; i<len;i++){
            System.out.println(str[i]);
        }
    }
}