题解 | #字符串的排列#

比较简单的回溯解题思路，可以参考 leetcode 全排列 这题。不同的是本题需要加上判断是否重复的条件

解题思路：

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
       char[] array = str.toCharArray();
        int len = array.length;
        boolean[] used = new boolean[len];
        ArrayList<String> res = new ArrayList<>();
        if (len <= 0) {
            return res;
        }
        LinkedList<Character> path = new LinkedList<>();
        dfs(array, len, 0, used, path, res);
        return res;
    }

    private void dfs(char[] array, int len, int depth, boolean[] used, LinkedList<Character> path, 
                    ArrayList<String> res) {
        if (depth == len) {
            StringBuilder sb = new StringBuilder();
            for (char c: path) {
                sb.append(c);
            }
            String s = sb.toString();
            if (!res.contains(s))
                res.add(s);
        }

        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                used[i] = true;
                path.add(array[i]);
                dfs(array, len, depth+1, used, path, res);
                used[i] = false;
                path.removeLast();
            }
        }
    }

}