题目描述

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

思路：递归

通过循环先固定字符串的首字符，然后将首字符后面的字符递归地进行排列

实现

    public ArrayList<String> Permutation(String str){
        //终止条件，只剩一个字符的情况，直接返回ArrayList结果
        if(str.length()==1){
            ArrayList<String> list=new ArrayList<>();
            list.add(str);
            return list;
        }

        ArrayList<String> list=new ArrayList<>();
        //递归
        //遍历str字符找不同的开头
        for(int i=0;i<str.length();i++){
            //去掉开头的字符,将后续的字符串进行递归.
            for(String s:Permutation(str.substring(0,i)+str.substring(i+1,str.length()))){
                list.add(str.charAt(i)+s);
            }
        }
        //利用HashSet进行去重,Collections的sort方法排序
        HashSet<String> hs = new HashSet(list);
        ArrayList<String> list_new=new ArrayList<>(hs);
        Collections.sort(list_new);
        return list_new;
    }