目錄

一、回溯算法基礎知識

二、分割回文串思路

2.1 如何切割

2.2 判斷回文

2.3 回溯三部曲?

2.4 其他問題

三、相關算法題目

四、總結

---

一、回溯算法基礎知識

詳見：代碼隨想錄刷題day46|（回溯算法篇）77.組合-CSDN博客

二、分割回文串思路

回溯遞歸法

兩個問題：1.如何切割？2.判斷回文？

2.1 如何切割

切割問題可以抽象成組合問題：取自代碼隨想錄

如何模擬切割線

切割線通過startIndex和 i 來模擬，表示當前處理的子串范圍；

2.2 判斷回文

利用雙指針法，一個從前往后遍歷字符串s，另一個從后往前遍歷字符串s，當兩者不等時，不是回文，返回false；否則返回true；

2.3 回溯三部曲?

①函數參數和返回值：返回為空void，參數傳入字符串s，以及每次遞歸遍歷時的起始位置startIndex；

②終止條件：遞歸的深度，樹的深度，何時結束遞歸：當切割到字符串的最后位置（s.length的位置）時，說明本次遞歸結束，將本次結果加入result結果集中，然后返回；

③單層遞歸邏輯：for循環中，startIndex 表示每次遞歸中開始遍歷的起始位置，i 從startIndex開始，逐漸+1，那么[startIndex, i] 就是要截取的子串；得到子串以后，首先判斷是否為回文，如果是，加入單個結果集 list 中，然后回退；如果不是，跳過本次循環，i++；

注意切割過的位置不能重復切割，所以遞歸中startIndex參數要傳入 i+1；

2.4 其他問題

遞歸循環中如何截取子串？

通過String的substring方法👇

public String substring(int beginIndex, int endIndex)

返回一個新字符串，它是此字符串的一個子字符串。該子字符串從指定的 beginIndex 處開始，直到索引 endIndex - 1 處的字符。因此，該子字符串的長度為 endIndex-beginIndex。

參數：beginIndex - 起始索引（包括）；endIndex - 結束索引（不包括）。

示例：

"hamburger".substring(4, 8)? ?returns "urge"

"smiles".substring(1, 5)? ? ? ? ? returns "mile"

三、相關算法題目

131.分割回文串

class Solution {List<String> list = new ArrayList<>();//存放單個結果List<List<String>> result = new ArrayList<>();//存放結果集合public List<List<String>> partition(String s) {backtracking(s,0);return result;}private void backtracking(String s, int startIndex){//如果起始索引已經超過子串長度 說明分割完畢 得到結果if(startIndex >= s.length()){result.add(new ArrayList<>(list));return;}//單層遞歸邏輯for(int i = startIndex;i < s.length();i++){//提取從startIndex 到 i 的子串String substring = s.substring(startIndex, i + 1);//判斷是否為回文if(isPalindrome(substring)){//是回文list.add(substring);backtracking(s, i+1);//遞歸處理剩余部分list.removeLast();//回溯 移除當前子串}}}//判斷一個字符串是否是回文private boolean isPalindrome(String s){int left = 0;int right = s.length() - 1;while(left < right){if(s.charAt(left) != s.charAt(right)){return false;}left++;right--;}return true;}
}

四、總結

1.本題難點：理解分割回文串 類似 組合問題，也可以抽象成樹的結構，深度代表遞歸的深度，寬度代表for循環；

2.切割的方式，也就是具體的樹結構是什么樣的？每一個節點；

3.終止條件，最后的葉子節點；

4.單層遞歸邏輯，每次截取的子串是哪里到哪里？

5.如何判斷一個字符串是否為回文；

6.如何截取子串；

7.這真的是中等題目嗎，自己想從一開始分割方式抽象成樹結構就錯咯😶