# 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 head = 0;
int tail = s.size() - 1;
while (head < tail)
{
if (s[head] != s[tail])
return false;
head++;
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 head = 0;
int tail = s.size() - 1;
while (head < tail)
{
if (s[head] != s[tail])
return false;
head++;
tail--;
}
return true;
}
vector<vector<string>> doPartition(string s, int head) {
vector<vector<string>> res;
if (head == s.size()) {
res.push_back(vector<string>());
return res;
}
if (memo.find(head) != memo.end())
return memo[head];
for (int i = head; i < s.size(); ++i) {
string curr = s.substr(head, i - head + 1);
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]);
}
}
memo[head] = res;
return res;
}
public:
vector<vector<string>> partition(string s) {
return doPartition(s, 0);
}
};
// DP.
class Solution {
private:
bool isPalindrome(string s) {
int head = 0;
int tail = s.size() - 1;
while (head < tail)
{
if (s[head] != s[tail])
return false;
head++;
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];
}
};