题目描述

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

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

提示：

• 1 <= s 的长度 <= 8

测试用例

用例1：

• 输入：s = "abc"
• 输出：["abc","acb","bac","bca","cab","cba"]

思路

回溯，排列，但是有相同元素，所以要用used数组来去重，同时，去重问题一定要对数据先进行排序

代码实现

/**
 * @param {string} s
 * @return {string[]}
 */

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入s: ");
s = readline();

var permutation = function (s) {
  function traversal(s, used) {
    if (path.length === s.length) {
      res.push([...path].join(""));
      return;
    }

    for (let i = 0; i < s.length; i++) {
      if (i > 0 && s[i] === s[i - 1] && used[i - 1] != 1) {
        continue;
      }
      // if(used[i] == 1){
      //     continue;
      // }
      if (used[i] != 1) {
        path.push(s[i]);
        used[i] = 1;
        traversal(s, used);
        used[i] = 0;
        path.pop();
      }
    }
  }
  let res = [];
  let path = [];
  if (s.length === 1) {
    return s.split("");
  }
  // 去重问题就要排序了
  s = s
    .split("")
    .sort((a, b) => {
      return a.localeCompare(b);
    })
    .join("");
  console.log("排序后的s: ", s);
  traversal(s, new Array(s.length).fill(0));
  return res;
};

const res = permutation(s);
console.log("res: ", res);

/* 
  请输入s:
  aab
  排序后的s:  aab
  res:  [ 'aab', 'aba', 'baa' ]

  请输入s:
  abc
  排序后的s:  abc
  res:  [ 'abc', 'acb', 'bac', 'bca', 'cab',
  'cba' ]

  请输入s:
  cba
  排序后的s:  abc
  res:  [ 'abc', 'acb', 'bac', 'bca', 'cab',
  'cba' ]
*/