[JS]字符串的排列

先用递归方法列出所有组合的可能。
递归逻辑：

1. 在当前str长度为n的情况下，提取出str[0]作为我们这一轮要插入的数。

2. 此时我们只要知道剩下n-1的排列组合，每一种组合从[0,length]依次插入str[0]得到新的排列组合。

   function calculate(arr){
    if(arr.length==1) return arr
    let res = calculate(arr.slice(1))//得到n-1所有的排列组合
    let final_res =[]
    for(let item of res){//挨个遍历每种组合
        for(let i = 0;i<=item.length;i++){//所有位置依次插入，形成新的组合
            final_res.push(item.slice(0,i)+arr[0]+item.slice(i,))
        }
    }

   在这一步之后，我们的排列组合会出现冲的情况，需要查重。
   在这里直接使用map，删掉重复。

    let map = new Map()
    for(let i=0;i<final_res.length;){
        if(!map.has(final_res[i])) {
            map.set(final_res[i],'');
            i++;
        }
        else {final_res.splice(i,1)}
   
    }
    return final_res.sort()

完整代码

function Permutation(str)
{
    // write code here

    let res = calculate(str)
    return res
}

function calculate(arr){
    if(arr.length==1) return arr
    let res = calculate(arr.slice(1))
    let final_res =[]
    for(let item of res){
        for(let i = 0;i<=item.length;i++){
            final_res.push(item.slice(0,i)+arr[0]+item.slice(i,))
        }
    }
    let map = new Map()
    for(let i=0;i<final_res.length;){
        if(!map.has(final_res[i])) {
            map.set(final_res[i],'');
            i++;
        }
        else {final_res.splice(i,1)}

    }


    return final_res.sort()
}