剑指Offer-字符的排列

发表于 | 阅读次数 | 阅读数

字符的排列

题目

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

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路

回溯法

代码

/**
* 题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。
例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba
*/
public class Permutation {
    public ArrayList<String> Permutation(String str){
        ArrayList<String> res = new ArrayList<>();
        if (str!=null&&str.length()>0){
            PermutationHelper(str.toCharArray(),0,res);
            Collections.sort(res);
        }
        return res;
    }

    private void PermutationHelper(char[] chars, int i, ArrayList<String> res) {
        if (i==chars.length-1){
            res.add(String.valueOf(chars));
        }else {
            Set<Character> set = new HashSet<>();
            for (int j=i;j<chars.length;j++){
                if (j==i||!set.contains(chars[j])){
                    set.add(chars[j]);
                    swap(chars,i,j);
                    PermutationHelper(chars,i+1,res);
                    swap(chars,i,j);//复位
                }
            }
        }
    }

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