字符串排列_27

public ArrayList<String> Permutation(String str) {
        List<String> res = new ArrayList<>();

        if (str == null || str.length() <= 1) {
            res.add(str);
            return (ArrayList<String>) res;
        }

        permutationHelper(str.toCharArray(), 0, res);
        Collections.sort(res);
        return (ArrayList<String>) res ;
    }


    //回溯法其实是在构造一棵生成树。对于"abc"，第一个位置有三种取值，第二个位置有两种取值，第三个位置有一种取值。
    private void permutationHelper(char[] arr, int index, List<String> res) {
        if (index == arr.length - 1 && !res.contains(String.valueOf(arr))) {
            res.add(String.valueOf(arr));
        }

        for (int i = index; i < arr.length; i++) {
            swap(arr,i,index);
            permutationHelper(arr,index+1,res);
            swap(arr,i,index);
        }
    }

    private void swap(char[] arr, int a, int b) {
        char temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }