题解 | #字符串的排列#

import java.util.*;
public class Solution {
    final int N = 10;
    ArrayList<String> res = new ArrayList<>();
    char[] chs;//储存字符串中的字符数组
    int step;//深搜树的最大深度，也就是递归终止步数
    int[] path = new int[N];
    boolean[] isVisited = new boolean[N];

    void dfs(int u) {
        if (u == step) {
            StringBuilder sbu = new StringBuilder();
            for (int i = 1; i <= step; i++) {
                sbu.append(chs[path[i] - 1]);
            }
            String s = sbu.toString();
            if (!res.contains(s)) {
                res.add(s);
            }
        }
        for (int i = 1; i <= step; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                path[u + 1] = i;
                dfs(u + 1);
                isVisited[i] = false;
            }
        }
    }

    public ArrayList<String> Permutation(String str) {
        chs = str.toCharArray();
        Arrays.sort(chs);//排序
        step = chs.length;
        dfs(0);//获取全排列，并根据全排列添加字符
        return res;
    }
}