專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

12月26日，華為宣布面向全球啟動2024奧林帕斯獎（OlympusMons Awards）懸紅難題征集。奧林帕斯獎由華為公司于2019年起設立，自設立以來，已吸引全球12個國家的超過240名學者參與，共評出5個奧林帕斯獎和13個奧林帕斯先鋒獎。

奧林帕斯難題百萬懸紅一般設立2個奧林帕斯獎，今年奧林帕斯獎獎金池還是保持了百萬級，設置2個奧林帕斯獎，獎金各100萬元；5個奧林帕斯先鋒獎，獎金各20萬元，總共300萬。大家有興趣的可以去嘗試一下，我就不參與了。

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第131題：分割回文串。

問題描述

來源：LeetCode第131題

難度：中等

給你一個字符串 s，請你將 s 分割成一些子串，使每個子串都是回文串。返回 s 所有可能的分割方案。

示例1：

輸入：s = "aab" 輸出：[["a","a","b"],["aa","b"]]

示例2：

輸入：s = "a" 輸出：[["a"]]

• 1 <= s.length <= 16

• s 僅由小寫英文字母組成

問題分析

這題讓把字符串分割成一些子串，并且要保證每個子串都是回文串，這是一道經典的回溯算法問題，關于回溯算法，可以看下很早之前寫的一篇文章 《》 。

對原字符串不斷的截取子串，如果子串是回文串就繼續截取，如果不是回文串就跳過，最后如果都截取完了，說明截取的子串都是回文串，把截取的子串保存下來即可。可以看到子串的截取就像一個 n 叉樹一樣，如下圖所示。

判斷子串是否是回文串，我們可以預處理，先計算好哪些子串是回文串哪些不是。如果 子串s [i, j ]是回文串，需要兩邊的字符相等s[i]==s[j]，并且中間的子串s[i+1,j-1]也必須是回文串。

JAVA：

public List
         
 > partition(String s) {     List > ans =  new ArrayList<>();      int length = s.length();      // 預處理，先計算子串中哪些是回文的，哪些不是，      // 數組dp[i][j]表示子串s[i,j]是否是回文的。      boolean[][] dp =  new  boolean[length][length];      for ( int j =  0; j < length; j++) {          for ( int i =  0; i <= j; i++) {              // 如果子串s[j,i]是回文串，則兩邊的字符s[i]和s[j]必須相同，并且              // 中間的子串s[i+1,j-1]如果存在，也必須是回文串。              if (s.charAt(i) == s.charAt(j) && (j - i <=  2 || dp[i +  1][j -  1]))                 dp[i][j] =  true;         }     }     backTrack(s, dp,  0, ans,  new ArrayList<>()); // 回溯算法      return ans; } private void backTrack(String s, boolean[][] dp, int index, List > ans, List  path)  {      // 邊界條件判斷，字符串s中的字符都訪問完了      if (index >= s.length()) {         ans.add( new ArrayList<>(path));          return;     }      for ( int i = index; i < s.length(); i++) {          // 如果當前截取的子串不是回文的，就跳過          if (!dp[index][i])  continue;          // 這里截取的子串s[index][i]就是回文串。         path.add(s.substring(index, i +  1)); // 做出選擇         backTrack(s, dp, i +  1, ans, path);  // 遞歸         path.remove(path.size() -  1); // 撤銷選擇     } }

C++：

public:
    vector

 > partition(string s) {         vector

 > ans;         int length = s.length();         // 預處理，先計算子串中哪些是回文的，哪些不是，         // 數組dp[i][j]表示子串s[i,j]是否是回文的。         vector

 > dp(length, vector

 (length, false));         for (int j = 0; j < length; j++) {             for (int i = 0; i <= j; i++) {                 // 如果子串s[j,i]是回文串，則兩邊的字符s[i]和s[j]必須相同，并且                 // 中間的子串s[i+1,j-1]如果存在，也必須是回文串。                 if (s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1]))                     dp[i][j] = true;             }         }         vector

  path{};         backTrack(s, dp, 0, ans, path);// 回溯算法         return ans;     }     void backTrack(string &s, vector

 > &dp, int index,                    vector

 > &ans, vector

  &path) {         // 邊界條件判斷，字符串s中的字符都訪問完了         if (index >= s.length()) {             ans.push_back(path);             return;         }         for (int i = index; i < s.length(); i++) {             // 如果當前截取的子串不是回文的，就跳過             if (!dp[index][i])                 continue;             // 這里截取的子串s[index][i]就是回文串。             path.push_back(s.substr(index, i - index + 1));// 做出選擇             backTrack(s, dp, i + 1, ans, path); // 遞歸             path.pop_back();// 撤銷選擇         }     }

Python：

def partition(self, s: str) -> List[List[str]]:
    def backTrack(index):
        # 邊界條件判斷，字符串s中的字符都訪問完了
        if index >= length:
            ans.append(path[:])
            return
        for i in range(index, length):
            # 如果當前截取的子串不是回文的，就跳過
            if not dp[index][i]:
                continue
            # 這里截取的子串s[index][i]就是回文串。
            path.append(s[index: i + 1])  # 做出選擇
            backTrack(i + 1)  # 遞歸
            path.pop()  # 撤銷選擇

    ans = []
    path = []
    length = len(s)
    # 預處理，先計算子串中哪些是回文的，哪些不是，
    # 數組dp[i][j]表示子串s[i,j]是否是回文的。
    dp = [[False] * length for _ in range(length)]
    for j in range(length):
        for i in range(j + 1):
            # 如果子串s[i,j]是回文串，則兩邊的字符s[i]和s[j]必須相同，并且
            # 中間的子串s[i+1,j-1]如果存在，也必須是回文串。
            if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
    backTrack(0)  # 回溯算法
    return ans

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。