131. 分割回文串

題目描述

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

回文串 是正著讀和反著讀都一樣的字符串。

示例 1：

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

示例 2：

輸入：s = “a”
輸出：[[“a”]]

提示：

• 1 <= s.length <= 16
• s 僅由小寫英文字母組成

回溯代碼

在此代碼片段中，子字符串是通過遞歸函數 backtracking 來獲取的。函數 backtracking 是一個回溯算法的實現，用于找到字符串 s 的所有可能的回文分割。回文分割是指將字符串分割成若干子串，使得每個子串都是回文的。

下面是 backtracking 函數在尋找子串時的詳細過程：

1. 函數 backtracking 接收原始字符串 s 和一個 startIndex 參數，該參數指示當前考慮的子串的起始位置。

2. 在每一層遞歸中，函數通過循環從 startIndex 遍歷到字符串 s 的末尾。

3. 在每次迭代中，它通過調用 isPalindrome 函數來檢查當前考慮的子串 s[startIndex, i] 是否是回文。

4. 如果檢測到子串是回文，使用 substr 方法從 s 中提取出回文子串。substr 方法的第一個參數是子串的起始位置，第二個參數是要提取的字符數。這里，提取的字符數計算為 i - startIndex + 1，表示從 startIndex 到 i（包含 i）的子串長度。

5. 獲取到的回文子串 str 被加入到臨時路徑 path 中。

6. 然后，遞歸調用 backtracking 函數，在尋找剩余子串的新的回文分割方案，此時 startIndex 更新為 i + 1，因為 i 位置的字符已經包含在了當前找到的回文子串內。

7. 遞歸返回后，執行 path.pop_back()，這是回溯的一部分，它將最后一個添加到 path 中的回文子串移除，以便 path 可以用于下一次循環迭代時的新的分割方案。

8. 當 startIndex 大于或等于字符串 s 的長度時，意味著已經到達字符串的末尾，當前 path 中存儲的回文子串序列即為 s 的一個有效分割，此時將 path 加入到 result 中。

通過這種方法，代碼實現了在遞歸循環中對字符串進行子串的分割，并確保了每個分割方案中的所有子串都是回文的。

假設我們有一個字符串 s = “aab” 并且我們想要找到所有可能的回文分割方案。下面是 backtracking 函數在這個字符串上操作的示例：

1. 初始調用 backtracking("aab", 0)，startIndex 是 0，意味著我們從字符串的第一個字符開始。

2. 第一層遞歸的循環從 i = 0 開始：

   a. 檢查子串 s[0, 0] 即 "a" 是否是回文 — 是，所以 path 變為 ["a"]。

   b. 遞歸調用 backtracking("aab", 1) 查看從第二個字符開始的所有回文分割方案。

3. 第二層遞歸開始，現在考慮的子串是 "ab"：

   a. 循環從 i = 1 開始，檢查子串 s[1, 1] 即 "a" 是否是回文 — 是，所以現在 path 變為 ["a", "a"]。

   b. 遞歸調用 backtracking("aab", 2) 查看從第三個字符開始的所有回文分割方案。

4. 第三層遞歸開始，現在考慮的子串是 "b"：

   a. 循環從 i = 2 開始，檢查子串 s[2, 2] 即 "b" 是否是回文 — 是，所以現在 path 變為 ["a", "a", "b"]。

   b. 遞歸調用 backtracking("aab", 3)，發現 startIndex 等于字符串長度，意味著找到了完整的一組分割方案。將其添加到 result 中，result = [["a", "a", "b"]]。

   c. 回溯發生，path.pop_back() 移除最后一個元素 "b"，現在 path = ["a", "a"]。

5. 返回到第二層遞歸，繼續 i 的循環，現在 i = 2：

   a. 檢查子串 s[1, 2] 即 "ab" 是否是回文 — 不是，所以不改變 path。

   b. 循環結束，開始回溯，path.pop_back() 移除最后一個元素 "a"，現在 path = ["a"]。

6. 返回到第一層遞歸，繼續 i 的循環，下一次 i = 1：

   a. 檢查子串 s[0, 1] 即 "aa" 是否是回文 — 是，所以 path 變為 ["aa"]。

   b. 遞歸調用 backtracking("aab", 2) 查看從第三個字符開始的所有回文分割方案。

7. 第四層遞歸開始，現在考慮的子串是 "b"：

   a. 循環從 i = 2 開始，檢查子串 s[2, 2] 即 "b" 是否是回文 — 是，所以 path 變為 ["aa", "b"]。

   b. 遞歸調用 backtracking("aab", 3)，發現 startIndex 等于字符串長度，意味著找到了另外一個完整的一組分割方案。將其添加到 result 中，現在 result = [["a", "a", "b"], ["aa", "b"]]。

8. 回溯發生，path.pop_back() 移除 "b"，回到 path = ["aa"]。然后第四層遞歸的循環結束，path.pop_back() 再次移除 "aa"，回到 path = []。

最終的 result 包含了所有可能的回文分割方案：[["a", "a", "b"], ["aa", "b"]]。這樣，我們就逐步構建了每一個可能的回文分割方案并將有效的方案添加到結果集中。

class Solution {
public:// 主函數，調用回溯函數并返回結果vector<vector<string>> partition(string s) {backstracking(s,0); // 從字符串的第一個字符開始進行回溯return result; // 返回所有可能的分割方案}private:vector<vector<string>> result; // 存儲所有可能的分割方案vector<string> path; // 用于存儲當前的分割方案// 檢查一個子串是否是回文串bool cheak(string& s,int begin,int end) {for(int i=begin,j=end;i<j;i++,j--) // 從兩頭開始向中間檢查if(s[i]!=s[j]) // 如果兩頭字符不相等，則不是回文return false; // 返回 falsereturn true; // 所有字符都相等，返回 true}// 回溯函數void backstracking(string& s,int start) {if(start==s.size()) { // 如果 start 等于字符串的長度，表示已經處理完畢result.push_back(path); // 將當前的分割方案添加到結果中return ; // 返回上一層}// 從 start 開始往后查找可能的分割點for(int i=start;i<s.size();i++) {if(cheak(s,start,i)) { // 檢查從 start 到 i 的子串是否是回文string str=s.substr(start,i-start+1); // 是，將其作為一個分割path.push_back(str); // 將子串添加到當前的分割方案中} else {continue; // 如果不是回文，跳過當前的字符，繼續下一輪循環}backstracking(s,i+1); // 遞歸調用，從下一個字符開始繼續分割剩余的字符串path.pop_back(); // 回溯，移除最后添加的子串，嘗試其他可能的分割點}}
};