题解 | #字符串的排列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    ArrayList<String> ans = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    public ArrayList<String> Permutation (String str) {
        int n = str.length();
        if(n == 0) return ans;
        char[] s = str.toCharArray();
        Arrays.sort(s);
        
        dfs(s, new boolean[n]);
        return ans;
    }

    void dfs(char[] s, boolean[] used) {
        if(path.length() == s.length) {
            ans.add(new String(path));
            return ;
        }

        for(int i = 0; i < s.length; i++) {
            if(used[i]) continue;

            if(i > 0 && s[i] == s[i - 1] && !used[i - 1]) continue; // 当前元素在前一层被选过了

            used[i] = true;
            path.append(s[i]);
            dfs(s, used);
            used[i] = false;
            path.deleteCharAt(path.length() - 1);
        }
    }
}