字符串的排列

function Permutation(str)
{
    // write code here
    str=str.split('').sort().join('')
    let res=[]
    let cur=''
    let visited={}
    function dfs(n){
        if(n==str.length) {
            res.push(cur)
            return 
        }
        for(let i=0;i<str.length;i++){
            if(i>0&&str[i]==str[i-1]&&!visited[i-1]) continue
            if(!visited[i]){
                 visited[i]=true
                 cur+=str[i]
                 dfs(n+1)
                 cur=cur.slice(0,cur.length-1)
                 visited[i]=false
            }  
        }
    }
    dfs(0)
    return res
}
module.exports = {
    Permutation : Permutation
};

function Permutation(str) {
 var result = [];
 if (str.length > 1) {
   //遍历每一项
   for (var m = 0; m < str.length; m++) {
     //拿到当前的元素
     var left = str[m];
     //除当前元素的其他元素组合
     var rest = str.slice(0, m) + str.slice(m + 1, str.length);
     //上一次递归返回的全排列
     var preResult = Permutation(rest);
     //组合在一起
     for (var i = 0; i < preResult.length; i++) {
       var tmp = left + preResult[i]
       result.push(tmp);
     }
   }
 } else if (str.length == 1) {
    result.push(str);
 }
 return [...new Set(result)];
}

function Permutation(str)
{
    // write code here
    //新建结果数组，初始化为空字符串
    let res = [''];
    //遍历给定字符串中的每一个字符
    for (const char of str) {
        //新建一个Set(可以起到剪枝、去重的作用)
        const temp = new Set();
        //对于res数组中的每个字符串
        for(const cur of res){
            //从尾到头依次操作
            for(let j = cur.length; j >=0; j--) {
                //插空
                temp.add(cur.slice(0,j)+char+cur.slice(j));
            }
        }
        //更新res
        res = [...temp];
    }
    // 返回处理完最后得到的res
    return res;
}
module.exports = {
    Permutation : Permutation
};

let result = new Set();

function Permutation(str)
{
    // write code here
    let arr = [...str];
    console.log(arr);
    
    insert('', arr);
    return [...result];
}

function insert(str, arr) {
    if(arr.length == 1) {
        let item = str + arr[0];
        console.log(typeof item)
        console.log(str, arr)
        result.add(item);
    } else {
        for(let i = 0; i < arr.length; i++) {
            let str2 = str + arr[i];
            let arr2 = [...arr];
            arr2.splice(i, 1);
            console.log(str2, arr2);
            insert(str2, arr2);
        }
    }
}

module.exports = {
    Permutation : Permutation
};

function Permutation(str)
{
    // write code here
    //保存每一轮递归的排列结果
    var result = [];
    //初始条件：长度为1
    if (str.length == 1) {
        return [str]
    } else {
        //求剩余子串的全排列,对每个排列进行遍历
        var preResult = Permutation(str.slice(1));
        for (let j = 0; j < preResult.length; j++) {
            for (let k = 0; k < preResult[j].length + 1; k++) {
                //将首字母插入k位置  
                let temp = preResult[j].slice(0, k) + str[0] + preResult[j].slice(k);
                result.push(temp);
            }
        }
        //return result.sort()//返回排序不去重
        return Array.from(new Set(result.sort())) //返回排序去重结果

    }

}
module.exports = {
    Permutation : Permutation
};

function Permutation(str)
{
    // write code here
    //保存每一轮递归的排列结果
    var result = [];
    //初始条件：长度为1
    if (str.length == 1) {
        return [str]
    } else {
        //求剩余子串的全排列,对每个排列进行遍历
        var preResult = Permutation(str.slice(1));
        for (let j = 0; j < preResult.length; j++) {
            for (let k = 0; k < preResult[j].length + 1; k++) {
                //将首字母插入k位置  
                let temp = preResult[j].slice(0, k) + str[0] + preResult[j].slice(k);
                result.push(temp);
            }
        }
        //return result.sort()//返回排序不去重
        return Array.from(new Set(result.sort())) //返回排序去重结果

    }

}
module.exports = {
    Permutation : Permutation
};

function Permutation(str)
{
    // write code here
    let res = []
    let len = str.length
    const flag = new Array(len).fill(false)
    str = str.split('').sort()
    backPack('')
    return res
    function backPack(s){
        if(s.length == len){
            res.push(s.slice())
            return 
        }
        for(let i = 0;i<str.length;i++){
            if(flag[i] || (i>0&&str[i] == str[i-1] &&!flag[i-1])){
                continue 
            }
            s += str[i]
            flag[i] = true
            backPack(s)
            flag[i] = false
            s = s.substring(0,s.length-1)
        }
    }
}

function Permutation(str) {
    if (str.length == 1) return str;
    let sx = [...str];
    let stra = [];
    for (let i = 0; i < sx.length; i++) {
        let sn = sx[i];
        sx.splice(i, 1);
        Permutation(sx).forEach(s => {
            if (stra.indexOf(sn + s) == -1)
                stra.push(sn + s);
        });
        sx = [...str];
    }
    return stra;
}

function Permutation(str)
{
    // write code here
    if(str.length==0){return false;}
    var result=[];
    if(str.length==1){
        return [str];
    }else{
        for(var i=0;i<str.length;i++){
            var c=str[i];//遍历str 拿到字符放首位 在与后面全排列拼接
            var newstr=str.slice(0,i)+str.slice(i+1,str.length);
            var r=Permutation(newstr);//递归剩余字符 返回数组
            for(var j=0;j<r.length;j++){
                var temp=c+r[j];//与全排列字符拼接
                result.push(temp);
            }
        }
    }
    return [...new Set(result)];//去重相同叠字符如'aaa'
}

js版本 递归版本思路会清晰点

/**
 * 我的解题思路：
 * 没有生命套路与技巧，完全是生解。。。。
 * 1.将字符串分解为字符数组，如果字符串不为空，则初始化结果集为数组的最后一个元素，否则初始化为空
 * 2.当字符数组不为空时，进行遍历
 * 3.获取字符数组的最后一个元素char，并移除原数组中该元素
 * 4.遍历结果集，将char与结果集中的每一个元素进行组合，对于长度为n的元素，共有n + 1种组合方式
 * 5.每次遍历完结果集后，将结果集修改为遍历后的结果，并用该结果进行再次遍历，直到字符数组为空
 * 6.对结果集进行字符排序并返回结果集
 *
 * @param {*} str 
 */
function Permutation(str)
{
    // write code here
    const array = str.split('');
    let result = array.length ? [array.pop()] : [];
    while (array.length) {
        const inner = [];
        const char = array.pop();
        result.forEach(item => {
            const temp = item.split('');
            for (let i = 0; i <= temp.length; i++) {
                temp.splice(i, 0, char);
                inner.indexOf(temp.join('')) === -1 && inner.push(temp.join(''));
                temp.splice(i, 1);
            }
        });
        result = inner;
    }
    return result.sort();
}

/**
 * 评论区TOP的解题思路：
 * 评论区热门的解题思路主要包括递归法及字典序排列法，这里给出字典序排列的解法
 * 1.将字符串分解为字符数组，如果字符串不为空，则初始化结果集为数组的最后一个元素，否则初始化为空
 * 2.从字符串数组的最右边开始，查找到第一个升序序列的位置i
 * 3.从位置i开始向右查找，查找到最后一个比第i位大的元素位j
 * 4.交换第i位和第j位的元素
 * 5.将第i + 1位之后的元素进行逆序
 * 6.将新的字符数组组成的字符串加入到结果集中并对新的字符数组进行遍历，重复2、3、4、5步直到i为0
 *
 * @param {*} str 
 */
function topPermutation(str)
{
    // write code here
    let array = str.split('');
    const result = str ? [array.sort().join('')] : [];
    let i = array.length - 1;
    while (i > 0) {
        i = array.length - 1;
        while (i > 0 && array[i - 1] >= array[i]) {
            i--;
        }
        let j = i;
        while (j < array.length && array[j] > array[i - 1]) {
            j++;
        }
        const temp = array[i - 1];
        array[i - 1] = array[j - 1];
        array[j - 1] = temp;
        const left = array.slice(0, i);
        const right = array.slice(i);
        array = left.concat(right.reverse());
        if (result.indexOf(array.join('')) === -1) {
            result.push(array.join(''));
        }
    }
    return result;
}

function Permutation(str) {
        var result = []
        if (str===''){ return result }
        var arr = str.split('')
        PermutationStr(arr, result, 0)
        var newResult = []
        for (i in result) {
            if (newResult.indexOf(result[i] === -1)) {
                newResult.push(result[i])
            }
        }
        // 排序
        return newResult.sort()
    }

    // 回溯的思想, 深度遍历, tag用来记录当前移动到下一位要交换的字符的下标
    function PermutationStr(array, result, tag) {
        // 当移动到最后一位时, 存储
        if(tag == array.length) {
            var temp = array.join('')
            // 判断有无重复
            if (result.indexOf(temp) == -1)
                result.push(temp)
        }
        for(var i=tag; i<array.length; i++) {
            // 判断有无重复相邻字符
            if (array[i]!==array[i+1]){
                // 包括自己和自己的交换
                swap(array, i, tag)
                PermutationStr(array, result, tag+1)
                // 交换回来??
                swap(array, i, tag)    
            }
        }
    }

    // 交换位置
    function swap(array, i, j) {
        var temp = array[i]
        array[i] = array[j]
        array[j] = temp
    }

function Permutation(str)
{
    if(str.length==0) return []
    var array = [str[0]]
    for(let j = 1;j<str.length;j++){
        array = f(array,str[j])
    }
    return [...new Set(array)].sort()
    /* 
     * 下面的 f 函数是向字符串数组 a 中插入一个新字符,返回新的全排列数组, 
     * 例如向['aa']插入'b'得到['baa','aba','aab'] 
    */
    function f(a,ch){
        var o = []
        for(let i=0;i<=a[0].length;i++){
            o = o.concat(a.map(x=>x.slice(0,i)+ch+x.slice(i)))
        }
        return [...new Set(o)]
    }
}