题解 | #字符串的排列#

import java.util.*;


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

    public void strCombination(StringBuilder sb, HashSet<String> set, String str, boolean[] flag){
        //如果长度相等，证明这个组合是满足的，添加到set中。
        if(sb.length() == str.length()){
            set.add(sb.toString());
            return;
        }

        for(int i = 0; i < str.length(); i++){
            //相同的字母的排列是一样的，已经排列过的字母不会再排列
            if((i > 0 && str.charAt(i) == str.charAt(i - 1) && flag[i - 1]) || flag[i])continue;
            sb.append(str.charAt(i));
            flag[i] = true;
            strCombination(sb, set, str, flag);
            sb.deleteCharAt(sb.length() - 1);
            flag[i] = false;
        }
    }
}