JZ27-字符串的全排列

class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<>();
        if (str == null || str.length() == 0) {
            return list;
        }
        helper(list, 0, str.toCharArray());
        Collections.sort(list);
        return list;
    }

    public void helper(ArrayList<String> list, int index, char[] s) {
        if (index == s.length - 1) {
            list.add(String.copyValueOf(s));
            return;
        }
        // for循环和swap的含义：对于“ABC”，
        // 第一次'A' 与 'A'交换，字符串为"ABC", pos为0， 相当于固定'A'
        // 第二次'A' 与 'B'交换，字符串为"BAC", pos为0， 相当于固定'B'
        // 第三次'A' 与 'C'交换，字符串为"CBA", pos为0， 相当于固定'C'
        for (int i = index; i < s.length; i++) {
            if (i == index || s[index] != s[i]) {  //a b a c d ... 这里的 a与a就无需交换了
                if (i != index) {
                    swap(s, index, i); // a [b c d]  -> b [a c d]  //第一次i == index，然后空交换一次。但是不这样 a a就不会进入循环，因为s[index] == s[i]
                }
                helper(list, index + 1, s);
                if (i != index) {
                    swap(s, index, i); //b [a c d] -> a [b c d] 要把a/b重新归位
                    // 回溯的原因：比如第二次交换后是"BAC"，需要回溯到"ABC"
                    // 然后进行第三次交换，才能得到"CBA"
                }
            }
        }
    }

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