Palindrome Partitioning
Question
Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.
Solution 1:
这道题的特点是求出具体的所有方案,非方案个数,所以不能使用DP,而且求所有的方案个数很容想到使用DFS的方法来实现。
遍历的方法就是前缀或者后缀法,每一次的DFS相当于切到第POS刀,然后只需要判断前缀是否为回文,然后在决定后续的DFS.
解题重点在于要构造出DFS的遍历树:
current = [] 临时遍历变量。
[]
[u'a'] [u'aa']
[u'a', u'a'] [u'aa', u'b'] add to result when pos == size of noms
[u'a', u'a', u'b'] add to result == size of nums
class Solution:
# @param s, a string
# @return a list of lists of string
def isPalind(self, s):
start, end = 0, len(s) - 1
while start < end:
if s[start] != s[end]:
return False
start += 1
end -= 1
return True
def isPalindrome(self, s):
for i in range(len(s)):
if s[i] != s[len(s)-1-i]: return False
return True
def dfs(self, result, current, s, pos):
if pos == len(s):
result.append(list(current))
for i in range(pos + 1, len(s) + 1):
prefix = s[pos:i]
if self.isPalindrome(prefix):
current.append(prefix)
self.dfs(result, current, s, i)
del current[-1]
def partition(self, s):
result = []
self.dfs(result, [], s, 0)
return result
Last updated
Was this helpful?