1 題目

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

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

示例 1：

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

示例 2：

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

2 解析

當我們在判斷 s[i…j] 是否為回文串時，常規的方法是使用雙指針分別指向 ii和 j，每次判斷兩個指針指向的字符是否相同，直到兩個指針相遇。然而這種方法會產生重復計算，例如下面這個例子：
當 s=aaba 時，對於前 2個字符aa，我們有 22種分割方法 [aa] 和 [a,a]，當我們每一次搜索到字符串的第i=2 個字符b 時，都需要對於每個 s[i…j] 使用雙指針判斷其是否為回文串，這就產生了重復計算。

因此，我們可以將字符串 s 的每個子串]s[i…j] 是否為回文串預處理出來，使用動態規劃即可。設f(i,j) 表示s[i…j] 是否為回文串，那麼有狀態轉移方程：

f ( i , j ) = { True , i ≥ j f ( i + 1 , j − 1 ) ∧ ( s [ i ] = s [ j ] ) , otherwise f(i, j) = \begin{cases} \texttt{True}, & \quad i \geq j \\ f(i+1,j-1) \wedge (s[i]=s[j]), & \quad \text{otherwise} \end{cases} f(i,j)={ True,f(i+1,j−1)∧(s[i]=s[j]),​i≥jotherwise​

​
其中∧ 表示邏輯與運算，即 s[i…j] 為回文串，當且僅當其為空串（i>j），其長度為 1（i=j），或者首尾字符相同且s[i+1…j−1] 為回文串。
預處理完成之後，我們只需要 O(1) 的時間就可以判斷任意 s[i…j] 是否為回文串了。

3 Python實現

class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
f = [[True]*n for _ in range(n)]
for i in range(n-1,-1,-1):
for j in range(i+1,n):
f[i][j] = (s[i]==s[j]) and f[i+1][j-1]
res = []
tmp = []
def dfs(i):
if i==n:
res.append(tmp[::])
return
for j in range(i,n):
if f[i][j]:
tmp.append(s[i:j+1])
dfs(j+1)
tmp.pop()
dfs(0)
return res