剑指Offer题解 - Day63

剑指 Offer 38. 字符串的排列

力扣题目链接[1]

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

分析：

首先，字符串的不重复排列一共有N * (N - 1) * ... * 1 种不同的方式。因此求此题的核心问题在于，如何进行字符的排列组合，并确保不重复（去除重复字符串）。

这里采用dfs的思路，对字符串进行搜索与回溯。先来看最终代码：

搜索与回溯

/**
 * @param {string} s
 * @return {string[]}
 */
const permutation = (s) => {
    let res = []; // 初始化结果数组
    let c = s.split(''); // 对字符串进行分割
    const dfs = (x) => { // 递归字符串
        if (x === c.length - 1) {
            res.push(c.join(''));
            return;
        }
        let set = new Set();
        for (let i = x; i < c.length; i++) {
            if (set.has(c[i])) continue;
            set.add(c[i]);
            [c[i], c[x]] = [c[x], c[i]]; // 交换元素
            dfs(x + 1);
            [c[x], c[i]] = [c[i], c[x]]; // 撤销交换
        }
    }
    dfs(0);
    return res;
};

• 时间复杂度 O(n!n)。
• 空间复杂度 O(n^2)。

分析：

代码的核心在于dfs的实现，下面就来具体分析。

首先越过递归终止条件往下看。每次进入到递归函数，需要初始化一个集合，用来存放已经遍历的字符。等到遍历后续字符时，遇到重复字符就可以跳过当前字符，执行下一次遍历。这也就是所谓的剪枝。可以考虑字符串'abb' ，当遍历到第二个'b'时，很明显是重复的，因此不需要字符拼接。而集合的目的就于防止重复的遍历。

如果当前元素不重复，那么就加入到集合中。注意循环的条件，i的起始值取决于参数x ，而x代表着当前哪个字符是固定的。循环的目的就是将固定位置之后的每个元素分别放到该固定位置上。

然后继续固定下一个位置。当回溯的时候，需要撤销刚才的元素交换，否则原字符串分隔的元素位置就会被改变。

直到固定的位置是字符串分割数组的最后一项时，意味着再也无需交换元素，此时的数组就是已经执行过交换操作并且不重复的，将该数组拼接成字符串并放入结果数组中。这也就是递归的终止条件。

最终返回结果数组即可。

总结

本题考查字符串的搜索与回溯。难度系数为困难。核心逻辑在于从头开始固定元素，并依次将后续元素与之交换，达到排列的目的。然后递归处理后续元素进行固定和交换。

复杂度方面，一共有N的阶乘种方案，字符串拼接操作需要时间复杂度为O(n) ，所以整体时间复杂度是O(n!n)。递归使用的调用栈大小为O(n) ，每次递归需要声明集合，总体来看，空间复杂度是O(n^2) 。

参考资料

[1]

力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5dfv5h/