leetcode(力扣) 131. 分割回文串（回溯）

文章目錄

• ​​題目描述：​​
• ​​思路分析：​​
• ​​完整代碼：​​

題目描述：

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

回文串 是正着讀和反着讀都一樣的字元串。

示例 1：

輸入：s = “aab”

輸出：[[“a”,“a”,“b”],[“aa”,“b”]]

示例 2：

輸入：s = “a”

輸出：[[“a”]]

思路分析：

這道題題意是找所有的分割方法。這個分割方法一定要搞清楚，意思就是所給的S字元串裡可以切任意刀，切完之後的子字元串都必須是回文串才行。傳回所有不重複的切割方法。

一開始我想着用滑動視窗做，後來發現，不太行，太複雜了 要考慮的情況非常多。

還是老老實實回溯吧。

先上我偷的圖，友善了解。

老規矩 回溯三步走：

1.确定函數參數：

這個題的參數比較好确定，一個是記錄路徑上元素的清單path，另一個就是回溯中常用的startindex了，這個參數就不多說了，之前的文章裡說了N邊啦。

2.确定終止條件

看上面我偷的那個圖，裡面的 ‘|’ 表示分割，顯然，當 分割符到字元串末尾的時候，表示分割完了，也就是到葉子節點了。

在之前的回溯中已經比較套路化了，for裡的i變量控制橫向，startindex控制縱向告訴下一層橫向的i從哪裡開始，是以實際上這裡的startindex就是切割點。(當切割點到最後了，也就是startindex到最後了，代表着結束)

是以終止條件就是 當 startindex == len(s)時，表示周遊到最後了，将path記錄的字元串加入到結果集。

完整代碼：

class Solution:
    def partition(self, s: str) -> List[List[str]]:
            res = []
            path = []
            def backtrack(path,startindex):
                # 确定終止條件
                # 當切割線切割到最後一位的時候表示到了葉子節點
                #  startindex相當于切割線
                if startindex == len(s):
                    res.append(path[:])
                # 回溯體
                for i in range(startindex,len(s)):
                    # 截取目前的字串判斷是否回文
                    temp = s[startindex:i+1]
                    if temp == temp[::-1]:
                        path.append(s[startindex:i+1])
                    else:
                        continue  # 但判斷不是回文的時候，再繼續本分支已經沒有意義了，因為是要截取子字元串，當其中一個不是回文，這個分支就可以扔了。 比如\A\AB\  這裡的AB已經不是回文了，再往下也沒意義了.
                        
                    backtrack(path,i+1)
                    path.pop()
            backtrack(path,0)
            return