第38题 – 字符串的排列

作者: 周伟林 分类: 剑指offer 发布时间: 2018-05-02 14:24

题目描述

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

解题思路

转化为求数组的全排列。
IO处理:split分解为数组,join合并为字符串。
实现一个函数help(arr, idxBegin),固定idxBegin之前的数据,让idxBegin与之后的数据依次交换一次。

jzoffer_t38

JavaScript实现

function Permutation(str)
{
    let arr = str.split(''), rel = [];
    if(arr.length === 0) return [];
    help(arr, 0);
    return rel.filter((item, idx, arr)=>idx===arr.indexOf(item)).sort();    // 数组去重,如['aa', 'aa']的情况!再排序。
    
    function help(arr, idxBegin){
        if(idxBegin === arr.length){
            rel.push(arr.join(''));
        }else{
            for(let i = idxBegin; i < arr.length; ++i){
                [arr[i], arr[idxBegin]] = [arr[idxBegin], arr[i]];    // 交换
                help(arr, idxBegin+1);
                [arr[i], arr[idxBegin]] = [arr[idxBegin], arr[i]];    // 恢复
            }
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注