# 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"]
]

class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> out;
helper(s, 0, out, res);
return res;
}
void helper(string s, int start, vector<string>& out, vector<vector<string>>& res) {
if (start == s.size()) { res.push_back(out); return; }
for (int i = start; i < s.size(); ++i) {
if (!isPalindrome(s, start, i)) continue;
out.push_back(s.substr(start, i - start + 1));
helper(s, i + 1, out, res);
out.pop_back();
}
}
bool isPalindrome(string s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) return false;
++start; --end;
}
return true;
}
};

class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
if (s.empty()) return {{}};
for (int i = 0; i < s.size(); ++i) {
if (!isPalindrome(s, i + 1)) continue;
for (auto list : partition(s.substr(i + 1))) {
list.insert(list.begin(), s.substr(0, i + 1));
res.push_back(list);
}
}
return res;
}
bool isPalindrome(string s, int n) {
for (int i = 0; i < n / 2; ++i) {
if (s[i] != s[n - 1 - i]) return false;
}
return true;
}
};

class Solution {
public:
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<string>> res;
vector<string> out;
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
if (s[i] == s[j] && (i - j <= 2 || dp[j + 1][i - 1])) {
dp[j][i] = true;
}
}
}
helper(s, 0, dp, out, res);
return res;
}
void helper(string s, int start, vector<vector<bool>>& dp, vector<string>& out, vector<vector<string>>& res) {
if (start == s.size()) { res.push_back(out); return; }
for (int i = start; i < s.size(); ++i) {
if (!dp[start][i]) continue;
out.push_back(s.substr(start, i - start + 1));
helper(s, i + 1, dp, out, res);
out.pop_back();
}
}
};

class Solution {
public:
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<vector<string>>> res(n + 1);
res[0].push_back({});
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
if (s[i] == s[j] && (i - j <= 2 || dp[j + 1][i - 1])) {
dp[j][i] = true;
string cur = s.substr(j, i - j + 1);
for (auto list : res[j]) {
list.push_back(cur);
res[i + 1].push_back(list);
}
}
}
}
return res[n];
}
};

Palindrome Partitioning II

Palindromic Substrings

https://leetcode.com/problems/palindrome-partitioning/

https://leetcode.com/problems/palindrome-partitioning/discuss/41982/Java-DP-%2B-DFS-solution

https://leetcode.com/problems/palindrome-partitioning/discuss/41963/Java%3A-Backtracking-solution.

https://leetcode.com/problems/palindrome-partitioning/discuss/41974/My-Java-DP-only-solution-without-recursion.-O(n2)

https://leetcode.com/problems/palindrome-partitioning/discuss/42103/Simple-backtracking-Java-solution-with-95-performance

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation