# 132. Palindrome Partitioning II

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

Return the minimum cuts needed for a palindrome partitioning of  s.

Example:

``````Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
``````

``````class Solution {
public:
int minCut(string s) {
if (s.empty()) return 0;
int n = s.size();
vector<vector<bool>> p(n, vector<bool>(n));
vector<int> dp(n);
for (int i = 0; i < n; ++i) {
dp[i] = i;
for (int j = 0; j <= i; ++j) {
if (s[i] == s[j] && (i - j < 2 || p[j + 1][i - 1])) {
p[j][i] = true;
dp[i] = (j == 0) ? 0 : min(dp[i], dp[j - 1] + 1);
}
}
}
return dp[n - 1];
}
};
``````

``````class Solution {
public:
int minCut(string s) {
if (s.empty()) return 0;
int n = s.size();
vector<vector<bool>> p(n, vector<bool>(n));
vector<int> dp(n);
for (int i = n - 1; i >= 0; --i) {
dp[i] = n - i - 1;
for (int j = i; j < n; ++j) {
if (s[i] == s[j] && (j - i <= 1 || p[i + 1][j - 1])) {
p[i][j] = true;
dp[i] = (j == n - 1) ? 0 : min(dp[i], dp[j + 1] + 1);
}
}
}
return dp[0];
}
};
``````

``````class Solution {
public:
int minCut(string s) {
if (s.empty()) return 0;
int n = s.size();
vector<int> dp(n + 1, INT_MAX);
dp[0] = -1;
for (int i = 0; i < n; ++i) {
for (int len = 0; i - len >= 0 && i + len < n && s[i - len] == s[i + len]; ++len) {
dp[i + len + 1] = min(dp[i + len + 1], 1 + dp[i - len]);
}
for (int len = 0; i - len >= 0 && i + len + 1 < n && s[i - len] == s[i + len + 1]; ++len) {
dp[i + len + 2] = min(dp[i + len + 2], 1 + dp[i - len]);
}
}
return dp[n];
}
};
``````

Palindrome Partitioning

Palindromic Substrings

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

https://leetcode.com/problems/palindrome-partitioning-ii/discuss/42213/Easiest-Java-DP-Solution-(97.36)

https://leetcode.com/problems/palindrome-partitioning-ii/discuss/42199/My-DP-Solution-(-explanation-and-code)

https://leetcode.com/problems/palindrome-partitioning-ii/discuss/42212/Two-C%2B%2B-versions-given-(one-DP-28ms-one-Manancher-like-algorithm-10-ms)

https://leetcode.com/problems/palindrome-partitioning-ii/discuss/42198/My-solution-does-not-need-a-table-for-palindrome-is-it-right-It-uses-only-O(n)-space.

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

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

×

Help us with donation