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

• « 上一篇：芯片测试（c语言）
• » 下一篇：Java面向对象三大特性之封装、继承、多态？