131. 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"]
]
Solution: DFS
class Solution(object):
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
partitions = dict()
palindromes = set()
def dfs(s):
if not s:
return [[]]
if s in partitions:
return partitions[s]
result = []
for end in xrange(1, len(s) + 1):
sub = s[:end]
if self.is_palindrome(sub, palindromes):
for partition in dfs(s[end:]):
result.append([sub] + partition)
partitions[s] = result
return result
dfs(s)
return partitions[s]
def is_palindrome(self, s, palindromes):
if s in palindromes:
return True
low = 0
high = len(s) - 1
while low < high:
if s[low] != s[high]:
return False
low += 1
high -= 1
palindromes.add(s)
return True
Lessons:
- Cache both known palindromes and partitions. Use string as the key, because same substring can appear in different positions. If we have a string
"aaabaaa", there are two"aaa", cache one and save the calculation for the other.