131. Palindrome Partitioning
https://leetcode.com/problems/palindrome-partitioning/
solution
切割问题其实是一种组合问题,但是要理解如何模拟切割。联想:切割一个点,和之前排列组合问题中的取一个树
注意:判断条件的时候,一种是判断整体是否满足条件,还有一种是判断每一步是否符合条件加入
为了不重复切割同一位置,start_index来做标记下一轮递归的起始位置(切割线)
class Solution:
def partition(self, s: str) -> List[List[str]]:
path = []
res = []
self.dfs(path, res, s, start=0)
return res
def dfs(self, path, res, s, start):
if start >= len(s):
res.append(path.copy())
return
for i in range(start, len(s)): # 注意范围
if self.is_valid(s, start=start, end=i): # 左闭右闭
path.append(s[start:(i+1)]) # 左闭右开
self.dfs(path, res, s, i+1)
path.pop()
def is_valid(self, string, start, end):
l = start
r = end
while r >= l:
if string[r] == string[l]:
r -= 1
l += 1
else:
return False
return True
时间复杂度:O(n⋅2^n) 空间复杂度:O(n⋅2^n)
class Solution:
def partition(self, s: str) -> List[List[str]]:
path = []
res = []
self.dfs(s, path, res, start=0)
return res
def dfs(self, s, path, res, start):
if start >= len(s):
res.append(path[:])
return
for i in range(start, len(s)):
temp = s[start:i+1]
if temp == temp[::-1]:
path.append(temp)
self.dfs(s, path, res, i+1)
path.pop()
else:
continue
follow up
Last updated