字符串的全排列

问题

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

地址：https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

递归

思路：从字符串中选出一个字符作为排列的第一个字符，然后对剩余的字符进行全排列。如此递归处理，从而得到所有字符的全排列。

分析：我们可以先根据一个实际的例子想想，怎样才能无遗漏的输出全排列：

两个数就不用说了，对于 ab，只有 ab 和 ba 两种
三个数，比如 abc，我们先分为三种情况，就是 a 开头，b 开头和 c 开头
对于 a 开头的情况，剩下 b 和 c，这就回到了两个数的排列；
对于 b 开头的情况，剩下 a 和 c，这也回到了两个数的排列；
c 开头的情况同理；
四个数，先按照开头分为四种情况，然后按照三个数的排列去处理
……
以此类推

由此可看出，这是一个递归。就好像求斐波那契数列的某一个元素，我们要先求出前面的；要想求出前面的，我们就要求出更前面的。记 “斐波那契数列的第 n 位” 这件事为 F(n)，则有 F(n) = F(n - 1) + F(n - 2)。

类似地，记 “求出 n 个字符串的全排列” 这件事为 P(n)，则有P(n) = 分别以这n个字符之一开头 + P(n - 1)。其中，P(n - 1) 表示去掉那个开头字符的剩余字符串的全排列。哪怕只有两个字符，比如对于上面例子中的 ab，同样符合这一条结论。

• 分析：以 'abc' 为例，执行步骤如下：

1. a 作为开头 -> 求 bc 全排列 -> 得到 bc 和 cb -> 与 a 合并 -> 得到 abc 和 acb
2. b 作为开头 -> 求 ac 全排列 -> 得到 ac 和 ca -> 与 b 合并 -> 得到 bac 和 bca
3. c 作为开头 -> 求 ab 全排列 -> 得到 ab 和 ba -> 与 c 合并 -> 得到 cab 和 cba

注：之前递归过程选择的字符，下一次不能再被选。

时间复杂度：O(n！)。

function permutation(str) {
    if(str.length == 0) {
        return [];
    }
    var result = [];
    var sortTemp = '';
    var arr = str.split('');
    // var len = arr.length;
    var result = sortString(arr, sortTemp, result);
    return result;

    function sortString(arr, sortTemp, res) {
        if(arr.length == 0) {
            return res.push(sortTemp);
        } else {
            let isRepeat = {};
            for(let i = 0; i < arr.length; i++) { // 不要用 len
                if(!isRepeat[arr[i]]) {
                    let temp = arr.splice(i, 1)[0]; // i 取出第i个字符作为第一个字符
                    sortTemp += temp;
                    sortString(arr, sortTemp, res); // 固定第一个字符的剩下字符的全排列已完成
                    arr.splice(i, 0, temp); // i 补全 恢复原字符串
                    sortTemp = sortTemp.slice(0, sortTemp.length - 1); // 清空sortTemp: 每次截掉字符串中的最后一个字符
                    isRepeat[temp] = true; // 相同的字符便不再在第一个字符中固定并对剩下的字符进行全排列了
                }
            }    
        }
        return res;
    }
}
permutation('abc')

这里固定字符串数组元素中的第一个字符的方式：是利用数组中splice()方法通过截取出来（删掉一个元素），完成全排列后再将该字符补全回原字符串中splice()（添加元素）的方式。遍历该字符串数组，依次截取掉每个字符元素的方式来作为字符串数组元素的第一个字符。

当然还可以通过依次向后交换的方式、或者取出元素以后向后插入的方式、以及经典的回溯法的方式等等。

References

leetcode题解(递归和回溯法)
July 算法习题 - 字符串4（全排列和全组合）