面试题 08.07. 无重复字符串的排列组合

面试题 08.07. 无重复字符串的排列组合

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
示例 1:
输入：S = “qwe” 输出：[“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]
示例 2:
输入：S = “ab” 输出：[“ab”, “ba”]
提示:

1. 字符都是英文字母。
2. 字符串长度在[1, 9]之间。

思路

常规回溯，将已经使用的标记，使用完以后取消标记即可。

解答

/**
 * @param {string} S
 * @return {string[]}
 */
var permutation = function (S) {
  let used = [];
  let res = [];
  let temp = "";
  const visit = () => {
    if (temp.length === S.length) {
      res.push(temp);
      return;
    }
    for (let i = 0; i < S.length; i++) {
      if (used[i]) continue;
      temp += S[i];
      used[i] = true;
      visit();
      used[i] = false;
      temp = temp.slice(0, -1);
    }
  };
  visit();
  return res;
};