字符串的全部排列

题目

统计信息：字数 2137 阅读5分钟

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

思路

考点：回溯算法（中等难度）；数组排序；数组去重

记录一个字符（temp），用于存储当前需要进入排列的字符

记录一个字符串（current），用于记录当前已经排列好的字符

记录一个队列（queue），用于存储还未被排列的字符

• 每次排列将temp添加到current
• 如果queue为空，则本次排列完成，将curret加入到结果数组中，结束递归
• 如果queue不为空，说明还有未排列的字符
• 递归排列queue中剩余的字符
• 为了不影响后续排列，每次递归完成，将当前递归的字符temp加回队列

代码

思路1：记录一个当前排列字符 temp（推荐，回溯算法）

function Permutation(str) {
  const result = [];
  if (str) {
    // 先将字符串转换成数组，执行回溯
    let queue = str.split('')
    PermutationCore(queue, result);
  }
  // 按照字典序排列
  result.sort();
  // 返回去重后的结果
  return [... new Set(result)];
}

function PermutationCore(queue, result, temp = "", current = "") {
  current += temp;
  if (queue.length === 0) {
    result.push(current);
    return;
  }
  for (let i = 0; i < queue.length; i++) {
    temp = queue.shift();
    PermutationCore(queue, result, temp, current);
    queue.push(temp);
  }
}

思路2：记录一个当前索引，不断交换数组中的元素（不太好理解，不推荐）

function Permutation(str) {
  var result = [];
  if (!str) {
    return result;
  }
  var array = str.split('');
  permutate(array, 0, result);
  result.sort();
  return [... new Set(result)];
}

function permutate(array, index, result) {
  if (array.length - 1 === index) {
    result.push(array.join(''));
  }
  for (let i = index; i < array.length; i++) {
    swap(array, index, i);
    permutate(array, index + 1, result);
    swap(array, i, index);
  }
}

---

Last update: November 9, 2024