面试题 08.08. 有重复字符串的排列组合

描述

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例1:

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

示例2:

 输入：S = "ab"
 输出：["ab", "ba"]

提示:

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

链接：https://leetcode.cn/problems/permutation-ii-lcci

解答

function permutation(str) {
  const results = [];
  const sortedStr = [...str].sort((a, b) => a > b ? 1 : -1).join('');

  dfs('', sortedStr, results);

  return results;
}

/*
 ""      "abc"
         "a"     "bc"
                 "ab"    "c"
                         "abc"   ""
                 "ac"    "b"
                         "acb"   ""
         "b"     "ac"
                 "ba"    "c"
                         "bac"   ""
                 "bc"    "a"
                         "bca"   ""
         "c"     "ab"
                 "ca"    "b"
                         "cab"   ""
                 "cb"    "a"
                         "cba"   ""
*/ 
function dfs(curr, rest, results, deep = 0) {
  //console.log('\t'.repeat(deep), JSON.stringify(curr), '\t', JSON.stringify(rest));

  if (rest.length === 0) {
    results.push(curr);
    return;
  }

  for (let i = 0, len = rest.length; i < len; i++) {
    // 去重
    if (i > 0 && rest[i] === rest[i-1]) {
      continue;
    }
    const newCurr = curr + rest[i];
    const newRest = rest.slice(0, i) + rest.slice(i + 1);


    dfs(newCurr, newRest, results, deep + 1);
  }
}


console.log(permutation('abc'))

参考

• 21.字符串的全排列 (opens new window)