题解 | #字符串的排列#

import java.util.*;

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

        // 边界情况
        if (str == null || str.length() == 0) {
            return res;
        }

        // 排序，注意这个是一个包含重复字符的排序
        boolean[] flag = new boolean[str.length()];
        StringBuffer list = new StringBuffer();
        char[] charStr = str.toCharArray();

        // 按字典序排序
        Arrays.sort(charStr);

        // 调用递归函数
        recursion(charStr, list, flag, res);
        return res;
    }

    private void recursion(char[] charStr, StringBuffer list, boolean[] flag, ArrayList<String> res) {
        if (list.length() == charStr.length) {
            res.add(new String(list));
            return;
        }

        for (int i = 0; i < charStr.length; i++) {
            // 跳过已使用的字符
            if (flag[i]) {
                continue;
            }
            // 跳过重复的字符
            if (i > 0 && charStr[i] == charStr[i - 1] && !flag[i - 1]) {
                continue;
            }
            list.append(charStr[i]);
            flag[i] = true;
            recursion(charStr, list, flag, res);
            // 回溯
            list.deleteCharAt(list.length() - 1);
            flag[i] = false;
        }
    }
}