LeetCode 熱題 100 | 131. 分割回文串

大家好，今天我們來解決一道經典的回溯算法問題——分割回文串。這道題在 LeetCode 上被標記為中等難度，要求將一個字符串 s 分割成若干個子串，使得每個子串都是回文串，并返回所有可能的分割方案。

---

問題描述

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

示例 1：

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

示例 2：

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

提示：

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

---

解題思路

核心思想

1. 回溯法：

   • 使用回溯法（Backtracking）來解決這個問題。
   • 從字符串的起始位置開始，嘗試所有可能的分割點，檢查每個子串是否為回文串。
   • 如果當前子串是回文串，則將其加入當前路徑，并繼續處理剩余部分。
   • 如果到達字符串的末尾，則將當前路徑加入結果列表。

2. 輔助函數：

   • 使用一個輔助函數 is_palindrome 來判斷一個子串是否為回文串。

3. 回溯過程：

   • 使用一個遞歸函數 backtrack，記錄當前路徑和處理到的位置。
   • 在每次遞歸調用中，嘗試所有可能的分割點，如果當前子串是回文串，則繼續遞歸處理剩余部分。

---

Python代碼實現

class Solution:def partition(self, s: str) -> List[List[str]]:def is_palindrome(sub):return sub == sub[::-1]def backtrack(start, path):if start == len(s):result.append(path[:])returnfor end in range(start + 1, len(s) + 1):if is_palindrome(s[start:end]):path.append(s[start:end])backtrack(end, path)path.pop()result = []backtrack(0, [])return result

代碼解析

1. 輔助函數：

   • is_palindrome(sub)：判斷子串 sub 是否為回文串。
   • 使用字符串反轉的方法 sub == sub[::-1] 來判斷。

2. 回溯函數：

   • backtrack(start, path)：從位置 start 開始，嘗試所有可能的分割點。
   • 如果到達字符串的末尾（start == len(s)），將當前路徑 path 加入結果列表 result。
   • 對于每個可能的分割點 end，檢查子串 s[start:end] 是否為回文串。
   • 如果是回文串，則將其加入當前路徑 path，并遞歸處理剩余部分。
   • 遞歸返回后，從路徑中移除最后一個子串（回溯）。

3. 主函數：

   • 初始化結果列表 result。
   • 調用 backtrack(0, [])，從字符串的起始位置開始處理。

復雜度分析

• 時間復雜度：O(2^n * n)，其中 n 是字符串 s 的長度。最壞情況下，每個位置都可能是一個分割點，需要嘗試所有可能的分割方案。
• 空間復雜度：O(n)，遞歸調用棧的深度最多為字符串的長度。

示例運行

示例 1

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

示例 2

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

---

總結

通過回溯法，我們可以高效地解決分割回文串問題。回溯法的核心在于嘗試所有可能的分割點，并通過輔助函數判斷子串是否為回文串。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！

關注我，獲取更多算法題解和編程技巧！