题解 | #字符串的排列#

回溯

import java.util.ArrayList;
import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       char[] c = str.toCharArray();
        Arrays.sort(c);
        str = String.valueOf(c);
        ArrayList<String> res = new ArrayList<>();
       StringBuilder sb = new StringBuilder();
       boolean[] visited = new boolean[str.length()];
       backTrack(str,res,sb,visited);
       return res;      
    }
    public void backTrack(String str,ArrayList<String> res,StringBuilder sb,boolean[] visited){
        if(sb.length() == str.length()){
            res.add(new String(sb.toString()));
        }
        for(int i = 0;i<str.length();i++){
            if(visited[i]){
                continue;
            }
            if(i>0&&str.charAt(i) == str.charAt(i-1)&&visited[i-1]==false){
                continue;
            }
            sb.append(str.charAt(i));
            visited[i] = true;
            backTrack(str,res,sb,visited);
            sb.deleteCharAt(sb.length()-1);
            visited[i] = false;
        }
    }
}