131. Palindrome Partitioning
131. Palindrome Partitioning
找出所有可能要用回溯
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
res = []
trace = []
self.DFS(s, res, trace, 0)
return res
def DFS(self, s, res, trace, k):
if k == len(s):
res.append(trace[:])
for i in range(k+1, len(s)+1):
if self.isValid(s[k:i]):
trace.append(s[k:i])
self.DFS(s, res, trace, i)
trace.pop()
def isValid(self, s):
return s and s == s[::-1]
132. Palindrome Partitioning II
132. Palindrome Partitioning II
求一个结果要用动态规划
class Solution(object):
def minCut(self, s):
"""
:type s: str
:rtype: int
"""
dp = [i for i in range(len(s))]
#dp[i]表示s[:i+1]需要几cut
for i in range(len(s)):
if self.isValid(s[:i+1]):
dp[i] = 0
else:
for j in range(1, i+1):
if self.isValid(s[j:i+1]):
dp[i] = min(dp[i], dp[j-1] + 1)
else:
dp[i] = min(dp[i], dp[j-1] + i - j + 1)
return dp[-1]
def isValid(self, s):
return s and s == s[::-1]
