image.png
0. 鏈接
1. 題目
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Example:
Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]
2. 思路1: 回溯+動(dòng)態(tài)規(guī)劃
- 基本思路是:
- 從左到右依次嘗試以每個(gè)字母作為回文的中心點(diǎn), 向左向右盡量擴(kuò)展, 如果從start到i構(gòu)成回文, 則記錄dp[i][start]=True, 然后繼續(xù)更新start為i+1, 繼續(xù)向右查找其他回文中心點(diǎn)
- 例如對(duì)于
abcba- 先嘗試從第0位的a作為回文中心點(diǎn), 則start=i=0, 記錄dp[0][0] = True
-
start先一直右移(深度優(yōu)先搜索), 不斷得到
dp[1][1] = dp[2][2] = dp[3][3] = dp[4][4] = True
, 得到第一組合法的回文列表['a', 'b', 'c', 'b', 'a'], 即每個(gè)字母單獨(dú)成為回文. - 接下來回溯倒數(shù)第二步, 即
start=3時(shí),i=3已經(jīng)遍歷過, 再嘗試i = 4, 則經(jīng)過判斷s[3] != s[4], 構(gòu)不成回文, 于是此次回溯失敗,start=3的可能情況已經(jīng)嘗試完畢 - 接下來繼續(xù)回溯
start=2的情況,i = 2已經(jīng)遍歷過, 接下來開始遍歷i=3,4, 對(duì)于i=3, 由于s[2] != s[3], 則回溯失敗; 對(duì)于i=4, s[2] != s[3], 也回溯失敗, 于是start=2的可能情況也已經(jīng)嘗試完畢 - 接下來繼續(xù)回溯
start=1的情況,i=1已經(jīng)嘗試過, 繼續(xù)嘗試i=2,3,4,s[start=1] != s[i = 2], 但s[start=1]==s[i = 3], 找到一個(gè)成功的結(jié)果, 則記錄dp[1][3] = True, 并得到分割結(jié)果['a', 'bcb', 'a'] - 同理
start=0的情況, 滿足s[start=0] == s[i=4]且dp[start + 1][i - 1] = dp[1][3] = True, 則直接記錄dp[0][4] = True, 并得到分割結(jié)果['abcba'] - 收集所有結(jié)果，得到返回值
[['a', 'b', 'c', 'b', 'a'], ['a', 'bcb', 'a'], ['abcba']]
- 分析:
- 過程中, 嘗試以每個(gè)節(jié)點(diǎn)作為start的時(shí)候, 由于回溯的存在, 對(duì)于每個(gè)start~n-1的元素, 都需要嘗試一遍, 因此時(shí)間復(fù)雜度是
O(n^2), 動(dòng)態(tài)規(guī)劃所用的dp耗費(fèi)存儲(chǔ)空間為O(n^2)
- 復(fù)雜度
- 時(shí)間復(fù)雜度
O(n^2) - 空間復(fù)雜度
O(n^2)
3. 代碼
# coding:utf8
from typing import List
class Solution:
def partition(self, s: str) -> List[List[str]]:
rtn_list = list()
path = list()
length = len(s)
dp = [[False] * length for _ in range(length)]
self.dfs(rtn_list, path, s, 0, length, dp)
return rtn_list
def dfs(self, rtn_list, path, s, start, length, dp):
if start == length:
rtn_list.append(path.copy())
else:
for i in range(start, length):
if s[start] != s[i]:
continue
if i - 1 > start + 1 and not dp[i - 1][start + 1]:
continue
dp[i][start] = True
path.append(s[start: i + 1])
self.dfs(rtn_list, path, s, i + 1, length, dp)
path.pop()
def my_test(solution, s):
print('input: s={}; output: {}'.format(s, solution.partition(s)))
solution = Solution()
my_test(solution, 'aab')
my_test(solution, 'bb')
輸出結(jié)果
input: s=aab; output: [['a', 'a', 'b'], ['aa', 'b']]
input: s=bb; output: [['b', 'b'], ['bb']]
4. 結(jié)果
image.png
