## # 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.

Example:

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

### # Solution

Approach 1: Recursion.

Approach 2: DP.

### # Code (Python)

Approach 1:

``````class Solution:
def partition(self, s):
"""
:type s: str
:rtype: List[List[str]]
"""
memory = {}
return self._partition(s, memory)

def _partition(self, s, memory):
if len(s) == 1:
return [[s]]
if s in memory:
return memory[s]
result = []
for i in range(1, len(s)):
if self._is_palindrome(s[:i]):
for part in self._partition(s[i:], memory):
result.append([s[:i]] + part)
if self._is_palindrome(s):
result.append([s])
memory[s] = result
return result

# can also do a O(N^2) prescan to look for palindromes (with dynamic programming and a 2D table)
def _is_palindrome(self, s):
return s[::-1] == s
``````

Approach 2:

### # Code (C++)

Approach 1:

``````// Recursion.
class Solution {
private:
vector<vector<string>> res;
bool isPalindrome(string s) {
int tail = s.size() - 1;
{
return false;
tail--;
}
return true;
}
void doPartition(string s, vector<string>& buf) {
if (s.size() == 0)
{
res.push_back(buf);
return;
}
for (int len = 1; len <= s.size(); ++len)
{
string curr = s.substr(0, len);
if (!isPalindrome(curr))
continue;
buf.push_back(curr);
doPartition(s.substr(len, s.size() - len), buf);
buf.pop_back();
}
}
public:
vector<vector<string>> partition(string s) {
vector<string> buf;
doPartition(s, buf);
return res;
}
};
``````

Approach 2:

``````class Solution {
private:
unordered_map<int,vector<vector<string>>> memo;
bool isPalindrome(string s) {
int tail = s.size() - 1;
{
return false;
tail--;
}
return true;
}
vector<vector<string>> doPartition(string s, int head) {
vector<vector<string>> res;
res.push_back(vector<string>());
return res;
}
for (int i = head; i < s.size(); ++i) {
if (!isPalindrome(curr))
continue;
vector<vector<string>> buf = doPartition(s, i + 1);
for (int i = 0; i < buf.size(); ++i) {
buf[i].insert(buf[i].begin(), curr);
res.push_back(buf[i]);
}
}
return res;
}
public:
vector<vector<string>> partition(string s) {
return doPartition(s, 0);
}
};
``````
``````// DP.
class Solution {
private:
bool isPalindrome(string s) {
int tail = s.size() - 1;
{
return false;
tail--;
}
return true;
}
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
int sSize = s.size();
if (sSize == 0)
return res;
vector<vector<string>> memo[sSize+1] = {vector<vector<string>>(1, vector<string>())};
for (int i = 1; i <= sSize; ++i)
{
for (int j = 1; j <= i; ++j)
{
string curr = s.substr(j - 1, i - j + 1);
if (!isPalindrome(curr))
continue;
vector<vector<string>> newSet = memo[j-1];
for (int k = 0; k < newSet.size(); ++k)
{
newSet[k].push_back(curr);
memo[i].push_back(newSet[k]);
}
}
}
return memo[sSize];
}
};
``````