Palindrome Partitioning - LeetCode
Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. A palindrome string is a string that reads the same backward as forward.
Example 1: Input: s = “aab” Output: [[“a”,“a”,“b”],[“aa”,“b”]]
- code pass string
class Solution:
def partition(self, s: str) -> List[List[str]]:
res = []
def isPalindrome(inp):
return inp == inp[::-1]
def dfs(s, path):
if not s:
res.append(path)
for i in range(1, len(s)+1):
if isPalindrome(s[:i]):
dfs(s[i:], path + [s[:i]])
dfs(s, [])
return res
- code pass index
class Solution:
def partition(self, s: str) -> List[List[str]]:
res = []
def isPalindrome(inp):
return inp == inp[::-1]
def dfs(start, path):
if start == len(s):
res.append(path)
for i in range(start, len(s)):
if isPalindrome(s[start:i + 1]):
dfs(i + 1, path + [s[start:i + 1]])
dfs(0, [])
return res
- code to show append/pop, compare to path + []
class Solution:
def partition(self, s: str) -> List[List[str]]:
res = []
def isPalindrome(inp):
return inp == inp[::-1]
def dfs(start, path):
if start == len(s):
res.append(path[:])
for i in range(start, len(s)):
if isPalindrome(s[start:i + 1]):
path.append(s[start:i+1])
dfs(i + 1, path)
path.pop()
dfs(0, [])
return res
- code use memo to check start and end to determine isPalindrome
class Solution:
def partition(self, s: str) -> List[List[str]]:
def dfs(start, path, memo):
if start == len(s) : res.append(path)
for i in range(start, len(s)):
if s[start] == s[i] and (i - start <=2 or memo[(start + 1, i - 1)]):
memo[(start, i)] = True
dfs(i+1, path + [s[start:i+1]], memo)
memo = defaultdict(bool)
res = []
dfs(0, [], memo)
return res