题目描述

题解

回溯算法

常规的回溯算法思路, 需要注意的有以下几点:

为了方便记录可行字符串, 使用了动态列表, 但是这道题让返回的是String[], 可以使用方法res.toArray(new String[0])
因为所给的字符串可能会有重复字符的情况, 所以需要考虑降重的操作

public String[] permutation(String s) {
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();

    char[] charArray = s.toCharArray();
    Arrays.sort(charArray);
    int len = s.length();
    boolean[] used = new boolean[len];
    dfs(charArray, 0, res, path, len, used);
    return res.toArray(new String[0]);
}

private void dfs(char[] charArray, int depth, List<String> res, StringBuilder path, int len, boolean[] used) {
    if (depth == len) {
        res.add(path.toString());
        return;
    }

    for (int i = 0; i < len; i++) {
        if (!used[i]) {

            if (i > 0 && charArray[i] == charArray[i - 1] && !used[i - 1]) {
                continue;
            }

            path.append(charArray[i]);
            used[i] = true;

            dfs(charArray, depth + 1, res, path, len, used);
            used[i] = false;
            path.deleteCharAt(path.length() - 1);
        }
    }

}