题解 | #字符串的排列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
        StringBuilder strb = new StringBuilder(str);
        ArrayList<String> res = dfs(strb);
        HashSet<String> set = new HashSet<>(res);
        res.clear();
        res.addAll(set);
        return res;
    }
    ArrayList<String> dfs(StringBuilder str) {
        ArrayList<String> res = new ArrayList<>();
        if (str.length() == 1) res.add(str.toString());
        else {
            for (int i = 0; i < str.length(); i ++) {
                if (i == 0 || str.charAt(i) != str.charAt(0)) {
                    char temp = str.charAt(i);
                    str.setCharAt(i, str.charAt(0));
                    str.setCharAt(0, temp);
                    ArrayList<String> newResult = dfs(new StringBuilder(str.substring(
                                                      1)));
                    for (int j = 0; j < newResult.size(); j++)
                        res.add(str.substring(0, 1) + newResult.get(j));
                    //用完还是要放回去的
                    temp = str.charAt(0);
                    str.setCharAt(0, str.charAt(i));
                    str.setCharAt(i, temp);
                }
            }
        }
        return res;
    }

}