首页 > 代码库 > Palindrome Partitioning
Palindrome Partitioning
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
For example, given s = "aab",
Return
[ ["aa","b"], ["a","a","b"]]
又是一道回文的题目，回文系列有非常多的题目，主要是DP＋search的思路。这题也是。
先用DP求一个是否回文的状态矩阵，之后根据这个状态矩阵做dfs+backtracking；当然也可以一边DP，一边组织结果，针对结尾位置保存一个数组，每次可以针对当前回文字符加上之前那个位置有的所有组合做一个组合（https://discuss.leetcode.com/topic/2884/my-java-dp-only-solution-without-recursion-o-n-2）。
我的代码如下：
class Solution(object): def partition(self, s): """ :type s: str :rtype: List[List[str]] """ #first find the 2 dimension dp state #then search and backtracking to generate result. #dp order is very important dp = [[False]*len(s) for i in xrange(len(s))] for i in xrange(len(s)-1, -1, -1): #start for j in xrange(i, len(s)): #end if s[i] == s[j] and (i+1>j-1 or dp[i+1][j-1] == True): #核心判断语句 dp[i][j] = True res = [] self.helper(res, [], 0, dp, s) return res def helper(self, res, cur, index, dp, s): if index == len(s): res.append(cur+[]) return for i in xrange(index, len(s)): if dp[index][i] == True: cur.append(s[index:i+1]) self.helper(res, cur, i+1, dp, s) cur.pop()
Palindrome Partitioning
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。