题解 | #字符串的排列#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return string字符串一维数组
 */
function Permutation( str ) {
    // 字符串转换成数组并进行排序，使得重复元素相邻，方便后面去重处理
    const arr = [...str].sort();
    // res数组存放最后所有的结果
    const res = [];
    // path数组存放每次排列的结果
    const path = [];
    // used数组标识用过的元素
    const used = new Array(arr.length).fill(false);
    // 该函数的作用是基于当前的path继续进行字符选择，直到完成一次排列后，将其加入结果数组
    function getPermutation(path, used){
        // 如果path的长度（一次排列的长度）等于原始字符串数组长度，说明本次排列完成，将其转换为字符串后加入到结果数组res中
        if(path.length === arr.length){
            let resStr = path.join('');
            res.push(resStr);
            return;
        }
        for(let i = 0; i < arr.length; i++){
            // 已经用过的元素跳过
            if(used[i]) continue;
            // 为了避免重复，如果当前字符与前一个字符相同且前一个字符已经使用过，则跳过当前字符
            if(i > 0 && arr[i - 1] === arr[i] && used[i - 1]) continue;
            // 如果当前元素没用过则加入到排列结果中，并将其标识为已访问
            path.push(arr[i]);
            used[i] = true;
            // 基于当前元素进行递归
            getPermutation(path, used);
            // 递归结束后回溯，将最后添加的数弹出来并撤销标识
            path.pop();
            used[i] = false;
        }
    }
    getPermutation(path, used);
    return res;
}
module.exports = {
    Permutation : Permutation
};