前言

給定一個字符串，輸出該字符串中字符的所有排列。例如，輸入字符串"abc"，則輸出由字符a、b、c所能排列出來的所有字符串a(chǎn)bc、acb、bac、bca、cab、cba。

本文就跟大家分享下這個問題的解決方案，歡迎各位感興趣的開發(fā)者閱讀本文。

實(shí)現(xiàn)思路

相信很多開發(fā)者看到這個問題都會腦子一片空白，找不到入手之處。那我們就嘗試下把這個復(fù)雜的問題分解成小問題，比如，我們把一個字符串看成兩部分組成：

• 第一部分是當(dāng)前需要進(jìn)行組合的元素
• 第二部分是剩余的元素（除去當(dāng)前元素）

如下圖所示，我們從字符串的起始部位開始分析。

• 第一輪：

• 我們?nèi)〕龅?個字符"c"，當(dāng)前需要進(jìn)行組合的字符是"a"，拼接后，我們得到了"ac"
• 緊接著，我們?nèi)〕鍪Ｓ嘧址械淖詈笠粋€字符"b"，當(dāng)前需要進(jìn)行組合的字符是"ac"，拼接后，我們就得到了"acb"。剩余字符為空，我們就得到了第二個組合 ?acb?
• 剛開始的時候，需要進(jìn)行組合的字符是空字符，剩余的字符就是"abc"
• 緊接著，我們?nèi)〕鍪Ｓ嘧址牡?號位置的字符"a"作為當(dāng)前需要進(jìn)行組合的字符，剩余的字符就為"bc"
• 隨后，我們再取出剩余字符的第0號位置的字符"b"，上一步我們得到的需要組合的字符是"a"，把上一步得到的字符與現(xiàn)在取出的字符進(jìn)行拼接，我們就得到了"ab"，剩余的字符為"c"
• 最后，我們?nèi)〕鍪Ｓ嘧址凶詈笠粋€字符"c"，上一步我們得到的組合是"ab"，將其拼接后，我們得到了"abc"。剩余字符為空，我們就得到了第一個組合 ?abc?
• 我們在第二步的時候，剩余字符總共有兩個字符"bc"，上面我們只取出了第0個字符進(jìn)行組合，我們還需要取出它的其他字符完成組合。
• 至此，我們已經(jīng)訪問了所有位置的剩余字符訪問，本輪任務(wù)執(zhí)行完成

• 第二輪：

• 取出第1個字符"c"，當(dāng)前需要進(jìn)行組合的字符是"b"。拼接后，我們得到了"bc"，剩余的字符為"a"

• 取出最后一個剩余字符"a"，當(dāng)前需要進(jìn)行組合的字符是"bc"。拼接后，我們得到了"bca"，剩余字符為空，我們就得到了第四個組合 ?bca?

• 
  

  同樣的，剛開始我們需要進(jìn)行組合的字符為空，剩余的字符為"abc"

  
  

• 
  

  緊接著，我們?nèi)〕鍪Ｓ嘧址牡?號位置的字符"b"作為當(dāng)前需要進(jìn)行組合的字符，剩余的字符就為"ac"。

  
  

• 
  

  取出剩余字符的第0號元素"a"，上一步我們得到的需要進(jìn)行組合的字符為"b"，將他們拼接后，得到了"ba"，剩余的字符為"c"

  
  

• 
  

  繼續(xù)去除最后一個剩余字符"b"，上一步我們得到的需要進(jìn)行組合的字符為"ba"，拼接后，我們得到了"bac"，剩余字符為空，我們就得到了第三個組合 ?bac?

  
  

• 
  

  同樣的，我們在第二步的時候，剩余字符中有多個元素，我們只取了第0號位置的元素，需要把其他的字符也取出來完成組合

  
  

• 
  

  至此，我們訪問完了所有位置的剩余字符，本輪任務(wù)執(zhí)行完成

  
  

• 
  

  第三輪，分析到這里我相信大家已經(jīng)找到了規(guī)律，此處的分析就交給讀者來完成，幫助你更好的理解這個規(guī)律??。

  
  

image-20230220073230627

總結(jié)思路

通過上面的分析，相信很多開發(fā)者已經(jīng)聯(lián)想到了回溯算法。沒錯，這就是最典型的回溯算法，具體的實(shí)現(xiàn)思路為：

• 回溯函數(shù)接受2個參數(shù)：當(dāng)前需要進(jìn)行組合的字符、剩余字符
• 遞歸的基線條件為：剩余字符為空
• 遍歷剩余字符

• 將當(dāng)前需要進(jìn)行組合的字符與當(dāng)前遍歷到的字符進(jìn)行拼接，得到回溯函數(shù)的第1個參數(shù)
• 從剩余字符中除去剛才已經(jīng)拼接了的字符，將剩下的字符進(jìn)行拼接，得到回溯函數(shù)的第2個參數(shù)
• 兩個參數(shù)都得到后，開始遞歸調(diào)用回溯函數(shù)

• 遍歷到剩余字符的末尾后，我們就得到了這個問題的解（找到了目標(biāo)字符串的所有字符排列）

實(shí)現(xiàn)代碼

思路捋清楚之后，很容易就能將其轉(zhuǎn)換為代碼。

• 回溯函數(shù)的實(shí)現(xiàn)

/**
   * 使用回溯實(shí)現(xiàn)對字符的排列
   * @param current 當(dāng)前字符
   * @param remaining 剩余的字符
   * @private
   */
  private backtrack(current: string, remaining: string) {
    // 基線條件：剩余字符為空時則代表已經(jīng)完成本輪排列
    if (remaining.length === 0) {
      this.result.push(current);
      return;
    }
    // 用Set結(jié)合來標(biāo)記當(dāng)前字符是否已經(jīng)組合過
    const usedChars = new Set<string>();
    for (let i = 0; i < remaining.length; i++) {
      // 字符已經(jīng)出現(xiàn)過則跳過本輪循環(huán)
      if (usedChars.has(remaining[i])) {
        continue;
      }
      usedChars.add(remaining[i]);
      const nextCurrent = current + remaining[i];
      // 除當(dāng)前字符外的字符拼到一起
      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;
  }

注意：字符串中如果有重復(fù)字符，會造成重復(fù)的排列組合。因此，我們在實(shí)現(xiàn)回溯函數(shù)的時候，用Set集合對當(dāng)前遍歷到的字符進(jìn)行了標(biāo)記，如果已經(jīng)存在了就會跳過本輪循環(huán)，繼續(xù)找下一個字符。

測試用例

我們用文章開頭所列舉的例子來校驗(yàn)下上述代碼能否正確給出結(jié)果。

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