剑指Offer第二十七题：字符串的排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

解答：借鉴一下别人的方法，记录一下自己的理解。

思路：
1："a"和"b"肯定是不同的排列
2：通过交换字符来生成不同的排列
3：举例："abc"的全排列即{(a+"bc"的全排列),(b+"ac"的全排列),(c+"ab"的全排列)},就是将第一个字符和后面任意一个字符交换，一直递归至只剩一个字符。

public class Q_27 {

ArrayList<String> Permutation(String str) {
    ArrayList<String> list = new ArrayList<String>();
    if (str.length() >= 1) {
        PermutationHelper(str.toCharArray(), 0, list);
        Collections.sort(list);
    }
    return list;
}

private void PermutationHelper(char[] chars, int i, ArrayList<String> list) {
    if (i == chars.length - 1) {//只剩最后一个字符则添加到list
        list.add(String.valueOf(chars));
    } else {
        Set<Character> set = new HashSet<>();
        for (int j = i; j < chars.length; j++) {//循环交换后续的每一个字符
            if (!set.contains(chars[j])) {//保证重复的字符不交换
                set.add(chars[i]);
                swap(chars, i, j);
                PermutationHelper(chars, i + 1, list);
                swap(chars, i, j);
            }
        }
    }
}
private void swap(char[] cs, int i, int j) {
    char temp = cs[i];
    cs[i] = cs[j];
    cs[j] = temp;
}

public static void main(String[] args) {
    System.out.println(new Q_27().Permutation("asdfghjk"));
}

}