题解 | #字符串的排列#

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<>();
        StringBuilder sub = new StringBuilder();
        char[] strs = str.toCharArray();
        Arrays.sort(strs);
        dfs(list,sub,strs,0,new boolean[strs.length]);
        return list;
    }
    
    private void dfs(ArrayList<String> list, StringBuilder sub,char[] strs,int index,boolean[] vis){
        if(index == strs.length) {
            list.add(sub.toString());
            return ;
        }
        
        for(int i = 0; i < strs.length; i++){
            if(i > 0 && strs[i-1] == strs[i] && !vis[i-1] || vis[i]) continue;
            sub.append(strs[i]);
            vis[i] = true;
            dfs(list,sub,strs,index + 1,vis);
            vis[i] = false;
            sub.deleteCharAt(index);
        }
        
    }
    
}