侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 168 篇文章
  • 累计创建 25 个标签
  • 累计收到 217 条评论

目 录CONTENT

文章目录

实现字符串的排列算法

神奇的程序员
2023-02-22 / 0 评论 / 28 点赞 / 1,624 阅读 / 2,849 字 正在检测是否收录...

前言

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

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

实现思路

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

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

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

  • 第一轮:

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

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

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

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

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

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

      • 取出第1个字符"c",当前需要进行组合的字符是"b"。拼接后,我们得到了"bc",剩余的字符为"a"
      • 取出最后一个剩余字符"a",当前需要进行组合的字符是"bc"。拼接后,我们得到了"bca",剩余字符为空,我们就得到了第四个组合**bca**
    • 至此,我们访问完了所有位置的剩余字符,本轮任务执行完成

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

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);

image-20230222225804253

写在最后

至此,文章就分享完毕了。

我是神奇的程序员,一位前端开发工程师。

如果你对我感兴趣,请移步我的个人网站,进一步了解。

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于神奇的程序员公众号,未经许可禁止转载💌
28

评论区