实现字符串的实现算法排列算法

作者：神奇的程序员 2023-02-26 22:33:32开发 前端 字符串中如果有重复字符，会造成重复的字符排列组合。因此，排列我们在实现回溯函数的实现算法时候，用Set集合对当前遍历到的字符字符进行了标记，如果已经存在了就会跳过本轮循环，排列继续找下一个字符。实现算法

前言

给定一个字符串，字符输出该字符串中字符的排列所有排列。例如，实现算法输入字符串"abc"，字符则输出由字符a、排列b、实现算法c所能排列出来的字符所有字符串abc、acb、排列bac、bca、cab、cba。

本文就跟大家分享下这个问题的解决方案，欢迎各位感兴趣的开发者阅读本文。

实现思路

相信很多开发者看到这个问题都会脑子一片空白，找不到入手之处。那我们就尝试下把这个复杂的问题分解成小问题，比如，我们把一个字符串看成两部分组成：

• 第一部分是当前需要进行组合的元素
• 第二部分是剩余的元素（除去当前元素）

如下图所示，我们从字符串的起始部位开始分析。

• 第一轮：

• 我们取出第1个字符"c"，当前需要进行组合的字符是"a"，拼接后，我们得到了"ac"
• 紧接着，我们取出剩余字符中的最后一个字符"b"，当前需要进行组合的字符是"ac"，拼接后，我们就得到了"acb"。剩余字符为空，我们就得到了第二个组合 ​acb​
• 刚开始的时候，需要进行组合的字符是空字符，剩余的字符就是"abc"
• 紧接着，我们取出剩余字符的第0号位置的字符"a"作为当前需要进行组合的字符，剩余的字符就为"bc"
• 随后，我们再取出剩余字符的第0号位置的字符"b"，上一步我们得到的需要组合的字符是"a"，把上一步得到的字符与现在取出的字符进行拼接，我们就得到了"ab"，剩余的字符为"c"
• 最后，我们取出剩余字符中最后一个字符"c"，上一步我们得到的组合是"ab"，将其拼接后，我们得到了"abc"。剩余字符为空，我们就得到了第一个组合 ​abc​
• 我们在第二步的时候，剩余字符总共有两个字符"bc"，上面我们只取出了第0个字符进行组合，我们还需要取出它的其他字符完成组合。
• 至此，我们已经访问了所有位置的剩余字符访问，本轮任务执行完成

• 第二轮：

• 取出第1个字符"c"，当前需要进行组合的字符是"b"。拼接后，我们得到了"bc"，剩余的字符为"a"

• 取出最后一个剩余字符"a"，当前需要进行组合的字符是"bc"。拼接后，我们得到了"bca"，剩余字符为空，我们就得到了第四个组合 ​bca​

• 
  

  同样的，刚开始我们需要进行组合的字符为空，剩余的字符为"abc"

  
  

• 
  

  紧接着，我们取出剩余字符的第1号位置的字符"b"作为当前需要进行组合的字符，剩余的字符就为"ac"。

  
  

• 
  

  取出剩余字符的第0号元素"a"，上一步我们得到的需要进行组合的字符为"b"，将他们拼接后，得到了"ba"，剩余的字符为"c"

  
  

• 
  

  继续去除最后一个剩余字符"b"，上一步我们得到的需要进行组合的字符为"ba"，拼接后，我们得到了"bac"，剩余字符为空，我们就得到了第三个组合 ​bac​

  
  

• 
  

  同样的，我们在第二步的时候，剩余字符中有多个元素，我们只取了第0号位置的元素，需要把其他的字符也取出来完成组合

  
  

• 
  

  至此，我们访问完了所有位置的剩余字符，本轮任务执行完成

  
  

• 
  

  第三轮，分析到这里我相信大家已经找到了规律，此处的分析就交给读者来完成，帮助你更好的理解这个规律😋。

  
  

image-20230220073230627

总结思路

通过上面的分析，相信很多开发者已经联想到了回溯算法。没错，这就是最典型的回溯算法，具体的实现思路为：

• 回溯函数接受2个参数：当前需要进行组合的字符、剩余字符
• 递归的基线条件为：剩余字符为空
• 遍历剩余字符

• 将当前需要进行组合的字符与当前遍历到的字符进行拼接，得到回溯函数的第1个参数
• 从剩余字符中除去刚才已经拼接了的字符，将剩下的字符进行拼接，得到回溯函数的第2个参数
• 两个参数都得到后，开始递归调用回溯函数

• 遍历到剩余字符的末尾后，我们就得到了这个问题的解（找到了目标字符串的所有字符排列）

实现代码

思路捋清楚之后，很容易就能将其转换为代码。

• 回溯函数的实现

/**
* 使用回溯实现对字符的排列
* @param current 当前字符
* @param remaining 剩余的字符
* @private
*/
private backtrack(current: string, remaining: string) { 
// 基线条件：剩余字符为空时则代表已经完成本轮排列
if (remaining.length === 0) { 
this.result.push(current);
return;
}
// 用Set结合来标记当前字符是否已经组合过
const usedChars = new Set<string>();
for (let i = 0; i < remaining.length; i++) { 
// 字符已经出现过则跳过本轮循环
if (usedChars.has(remaining[i])) { 
continue;
}
usedChars.add(remaining[i]);
const nextCurrent = current + remaining[i];
// 除当前字符外的字符拼到一起
const nextRemaining = remaining.slice(0, i) + remaining.slice(i + 1);
this.backtrack(nextCurrent, nextRemaining);
}
}

• 获取字符串中所有字符的排列

public permute(str: string): Array<string> { 
this.result = [];
this.backtrack("", str);
return this.result;
}

注意：字符串中如果有重复字符，会造成重复的排列组合。因此，我们在实现回溯函数的时候，用Set集合对当前遍历到的字符进行了标记，如果已经存在了就会跳过本轮循环，继续找下一个字符。

测试用例

我们用文章开头所列举的例子来校验下上述代码能否正确给出结果。

const arrayOfStrings = new ArrayOfStrings();
const result = arrayOfStrings.permute("abc");
console.log(result);

责任编辑：武晓燕 来源： 神奇的程序员 字符串排列算法

(责任编辑：娱乐)