## Description

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

Example:

Input: "aab"
Output:
[
["aa","b"],
["a","a","b"]
]


## Solutions

### 1. Backtracking

# Time: O(nlogn)
# Space: O(n)
class Solution:
def partition(self, s: str) -> List[List[str]]:
if not s:
return []
res = []
self.dfs(s, [], res)
return res

def dfs(self, strs, path, res):
if not strs:
res.append(path)
return

n = len(strs)
for i in range(n):
if strs[:i+1] and self.is_palindrome(strs[:i+1]):
# print(i, strs, path)
# print(i, strs[i+1:], path+[strs[:i+1]])
self.dfs(strs[i+1:], path+[strs[:i+1]], res)

def is_palindrome(self, strs):
if not strs:
return True

n = len(strs)
l, r = 0, n-1
while l <= r:
if strs[l] != strs[r]:
return False
l += 1
r -= 1
return True
# 22/22 cases passed (104 ms)
# Your runtime beats 23.4 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)


更加精简的写法：

class Solution:
def partition(self, s):
res = []
self.dfs(s, [], res)
return res

def dfs(self, s, path, res):
if not s: # backtracking
res.append(path)
for i in range(1, len(s)+1):
if self.isPar(s[:i]):
self.dfs(s[i:], path+[s[:i]], res)

def isPar(self, s):
return s == s[::-1]
# 22/22 cases passed (88 ms)
# Your runtime beats 61.88 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13 MB)


### 2. DP

膜拜一下：

class Solution:
def partition(self, s):
if not s:
return [[]]
dp = {0:[[]], 1:[[s[0]]]}
for ii in range(1, len(s)):
dp[ii+1] = []
for jj in range(0, ii+1):
string = s[jj:ii+1]
if string == string[::-1]:
for sol in dp[jj]:
dp[ii+1].append(sol+[s[jj:ii+1]])
return dp[len(s)]
# 22/22 cases passed (60 ms)
# Your runtime beats 97.73 % of python3 submissions
# Your memory usage beats 5.88 % of python3 submissions (14.1 MB)