字符串的全排列问题

昨天小伙伴面试遇到了这样一题。

要求给出一个函数，输入是一个字符串比如 "abc" 要求输出这个字符串中所有字符的所有不重复的排列组合。也就是"abc" "bac" "bca" "acb" "cab" "cba";

当然看到算法题对于我来说就是崩溃的。因为想不到啊！

思路

当然 Google 了一番之后，看到别人的解释之后才想通了怎么去实现。

将字符串的第一个字符提出来

比如 abcd 就取出第一个字符 a

将第一个字符一次插入剩余字符之中

_b_c_d_ 就像是填空题，每次把 a 填入前面的横线中

对于 bcd 递归执行该方法，得到 bcd 的全排列，重复前面两步。

这里简化了很多，我的理解是将 a 看做一个整体， bcd 看做一个整体，而 bcd 在递归中又是相当于第一次调用的该函数的 abcd，取第一个字符 b 再对 cd 做全排列…依次进行下去。

代码

感觉解释的还是不清楚，可能是自己没有完全理解吧。

不多哔哔，上代码。

function permutation(str) {
    var len = str.length;
    var result = [];

    if (len === 1) {
        // 如果长度为 1 直接返回该字符串
        return [str];

    } else {
        // 每次对去除第一个字符后的字符串做全排列
        var prePermuation = permutation(str.slice(1));

        var preLength = prePermuation.length;
        // 第一个字符，即要插入队内的字符
        var curChar = str[0];
        // 循环将第一个字符插入全排列好的字符数组中
        for (let i = 0; i < preLength; i++) {

            var curStr = prePermuation[i];
            // 循环将第一个字符插入字符串中            
            for (let j = 0; j < prePermuation[0].length + 1; j++) {

                var tmp = curStr.substr(0, j) + curChar + curStr.slice(j);
                result.push(tmp);

            }

        }

   }
    // 数组去重，方法很多，只是 ES6 的写法行数少 :) 这不重要啦。
    return [...new Set(result)];
}

以后要多积累算法题，算法题一是靠智商，二是靠积累。我这种笨脑袋只好看看大牛的解法，然后去理解咯。