题解 | #字符串的排列#

转换为数字的全排列问题即可迎刃而解，将字符串转换为字符的下标数组，相同的字符以其第一次出现的下标为其替换的值

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
        ArrayList<String> result = new ArrayList<>();

        // 先将字符串转换为下标数组
        int n = str.length();
        int[] arr = new int[n];
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = str.charAt(i);
            Integer one = map.get(c);
            if (one != null) {
                arr[i] = one;
            } else {
                map.put(c, i);
                arr[i] = i;
            }
        }

        ArrayList<ArrayList<Integer>> temp = digitalPermute(arr);
        for (ArrayList<Integer> one : temp) {
            StringBuilder s = new StringBuilder();
            for (Integer index : one) {
                s.append(str.charAt(index));
            }
            result.add(s.toString());
        }

        return result;
    }

    // 数字的全排列算法
    public static ArrayList<ArrayList<Integer>> digitalPermute(int[] arr) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> current = new ArrayList<>();

        int n = arr.length;
        boolean[] used = new boolean[n];
        // 升序排序
        quickSort(arr, 0, n - 1);
        permuteHelper(arr, used, current, result);

        return result;
    }

    public static void permuteHelper(int[] arr, boolean[] used,
                                     ArrayList<Integer> current,
                                     ArrayList<ArrayList<Integer>> result) {
        int n = arr.length;
        if (current.size() == n) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < n; i++) {
            // 跳过重复元素
            if (used[i] || (i > 0 && arr[i] == arr[i - 1] && !used[i - 1])) continue;

            current.add(arr[i]);
            used[i] = true;
            permuteHelper(arr, used, current, result);
            used[i] = false;
            current.remove(current.size() - 1);
        }
    }

    // 快排算法
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = partition(arr, left, right);
            quickSort(arr, left, mid - 1);
            quickSort(arr, mid + 1, right);
        }
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= pivot) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) left++;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }
}