剑指 Offer 38. 字符串的排列

字符的全排列

题目链接-来源：力扣（LeetCode）

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

思路：

求全排列，容易联想到 DFS 以及回溯算法。输入的字符构成一个集合，从集合中依次取出元素作为开始，进行DFS，剪枝：忽略遍历过的字符。
对于输入字符的集合，我们可以用一个 StringBuilder 变量 res 来保存，这样我们可以按照索引指针每次「取」一个字符，同时也可以从 res 中删除该字符，完成回溯后再加回它，相当方便。取字符可以用一个 for 循环依次获取。为了防止结果出现重复，我们在 for 循环的同时维护一个 visited 集合，如果有相同字符，则会出现冲突，我们跳过该字符即可。
在每一层的 DFS 当中，我们还需要一个 StringBuilder 变量 construct 来收集当前生成的字符串。相对应地，完成回溯后，要把当前收集的这个字符删除掉。
DFS 跳出的条件就是 res 中已经没有字符了，此时我们将 construct 输出为一条字符串添加到结果列表当中。
当所有 DFS 都跳出时，我们也完成了对原字符串的全排列。
时间复杂度：O(n*n!)
空间复杂度：O(n²)

实现：

class Solution {
    public String[] permutation(String s) {
        StringBuilder res = new StringBuilder(s), cons = new StringBuilder();
        List<String> collect = new LinkedList<>();
        permuteHelper(res, cons, collect);
        return (String[]) collect.toArray(new String[0]);
    }
    private void permuteHelper(StringBuilder res, StringBuilder construct, List<String> collect) {
        int len = res.length();
        if (len == 0) {
            collect.add(construct.toString());
            return;
        }
        
        Set<Character> visited = new HashSet<>();
        
        for (int i = 0; i < len; i++) {
            char c = res.charAt(i);
            if (visited.contains(c)) {
                continue;
            }
            visited.add(c);
            res.deleteCharAt(i);
            construct.append(c);
            permuteHelper(res, construct, collect);
            construct.deleteCharAt(construct.length() - 1);
            res.insert(i, c);
        }
    }
}