27.字符串的排列

题目描述：

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = “abc”
输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof

解题思路：

• 首先说一下解题原理吧，这道题的原理比较难以理解，很难根据原理写出代码，所以还是要相应的记一下代码，原理和代码结合记忆就方便好多
• 我们创建一个字符串模板用来保存所有字符的类型，创建一个字典用于保存所有字符出现的次数
• 之后在回溯方法中我们需要记得首先保存当前的字符串用于后续的回溯，之后我们遍历字符串模板，取出对应的字符，已及对应字符的索引，判断其是否大于0，如果符合条件我们将其拼接到当前字符上，并让拼接后的字符继续回溯，退出回溯的条件是当前字符的长度为所给字符的长度，我们将其放入到我们的数组中
• 将之前的变量赋值给当前的字符并修改其出行的次数

解题代码：

function Permutation(str)
{
    // write code here
    if(str === '') return [];
    const map = new Map();
    let mapStr = '';
    for(let i = 0;i<str.length;i++) {
        if(!mapStr.includes(str[i])) {
            mapStr += str[i]
        }
        if(!map.has(str[i])) {
            map.set(str[i],1);
        }else {
            map.set(str[i],map.get(str[i]) + 1);
        }
    }
    const res = [];
    const backTrack = (s) => {
        if(s.length === str.length) {
            if(!res.includes(s)) {
                res.push(s);
                return;
            }
        }
        for(let i = 0;i < mapStr.length;i++) {
            // 查看字符剩余的个数
            let tempNum = map.get(mapStr[i]);
            // 记录当前字符用于回溯
            let pre = s;
            if(tempNum > 0) {
                s += mapStr[i];
                map.set(mapStr[i],map.get(mapStr[i]) - 1);
                backTrack(s);
                // 回溯
                s = pre;
                map.set(mapStr[i],tempNum);
            }
        }
    }
    backTrack('');
    return res;