LC. 131. 分割回文串


动态规划保存是否是回文串结果法
class Solution(object): def partition(self, s): """ :type s: str :rtype:
List[List[str]] """ res, sol = [],[] n = len(s) f = [[True]*n for i in range(n)]
for i in range(n-1,-1,-1): #倒序的目的是因为最后一行应该全是正确的，倒数第二行(n-2)开始比较两个字符是否相同，
#只需比较[n-2][n-1]也就是最后两个字符是否是回文。之后根据状态方程进行迭代比较 for j in range(i+1 , n): f[i][j] =
(s[i] == s[j]) and f[i+1][j-1] def backtrack(s, begin): if begin == n: res.
append(sol[:]) return for k in range(begin,n): if not f[begin][k]: continue sol.
append(s[begin:k+1]) backtrack(s,k+1) sol.pop() backtrack(s,0) return res
调用递归判断
class Solution(object): def partition(self, s): """ :type s: str :rtype:
List[List[str]] """ res, sol = [],[] n = len(s) def reverse(tmp): i,j = 0,len(
tmp)-1 while i < j: if tmp[i] != tmp[j]: return 0 i += 1 j -= 1 return 1 def
backtrack(s, begin): if begin == n: res.append(sol[:]) return for k in range(
begin,n): tmp = s[begin:k+1] if reverse(tmp) == 0: continue sol.append(tmp)
backtrack(s,k+1) sol.pop() backtrack(s,0) return res

技术
下载桌面版
GitHub
Microsoft Store
SourceForge
Gitee
百度网盘（提取码：draw）
云服务器优惠
华为云优惠券
京东云优惠券
腾讯云优惠券
阿里云优惠券
Vultr优惠券
站点信息
问题反馈
邮箱：[email protected]
吐槽一下
QQ群：766591547
关注微信
©2020-2025 ioDraw All rights reserved, Privacy Policy