《剑指offer》— JavaScript（27）字符串的排列

字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路

1. 递归思想：把大问题转换为若干小问题；
2. n个元素的全排列 = （n-1） 个元素全排列 + 一个元素作为前缀。
3. 递归的出口：只有一个元素的全排列，此时排序完成，输出数组。
4. 遍历字符串，将每个字符放在第一个元素作为前缀，并将其余元素继续全排列。
5. 新建一个isRepeat空对象，用来判断字符是否重复，若重复则跳过排序。

实现代码

function Permutation(str) {
    var result = [];
    if (str.length <= 0) {
        return [];
    }
    var sortTemp= "";
    var arr = str.split("");
    result = sortString(arr, sortTemp, []);
    return result;
}

function sortString(arr, sortTemp, res) {
    if (arr.length == 0) {
        res.push(sortTemp);
    } else {
        var isRepeat = {};
        for (var i = 0; i < arr.length; i++) {
            if (!isRepeat[arr[i]]) {
                var temp = arr.splice(i, 1)[0]; // 取出第i个字符
                sortTemp+= temp; // 第i个字符设为前缀
                sortString(arr, sortTemp, res);
                arr.splice(i, 0, temp); // 补全取出的元素，恢复原字符串
                sortTemp= sortTemp.slice(0, sortTemp.length - 1); // 清空sortTemp
                isRepeat[temp] = true;
            }
        }
    }
    return res;
}