题解 | #字符串的排列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
	  // Java中的String是不可变的，需要先转换成char数组再排序
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        str = new String(arr);
        ArrayList<String> ans = new ArrayList<>();
        boolean[] vis = new boolean[str.length()];
        dfs(str, 0, ans, new StringBuilder(), vis);
        return ans;
    }
    private void dfs(String s, int pos, ArrayList<String> ans, StringBuilder sb, boolean vis[]){
        if(pos == s.length()){
            ans.add(sb.toString());
            return;
        }
	  // 每次从第一个字母开始找可以使用的字母
        for(int i = 0; i < s.length(); i++){
		  // 当前字母已使用不可再用
            if(vis[i])continue;
		  // 相同字母先使用前面一个
            if(i > 0 && s.charAt(i) == s.charAt(i-1) && !vis[i-1])continue;
		  // 回溯法
            sb.append(s.charAt(i));
            vis[i] = true;
            dfs(s, pos+1, ans, sb, vis);
            sb.deleteCharAt(sb.length()-1);
            vis[i] = false;
        }
    }
}

排序+回溯