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

字符串的排列

题目描述

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

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路

递归思想：把大问题转换为若干小问题；
n个元素的全排列 = （n-1）个元素全排列 + 一个元素作为前缀。
递归的出口：只有一个元素的全排列，此时排序完成，输出数组。
遍历字符串，将每个字符放在第一个元素作为前缀，并将其余元素继续全排列。
新建一个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;

}

巴特西

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

字符串的排列

题目描述

思路

实现代码

最新文章

热门文章