Palindrome Partitioning II Problem
Description
LeetCode Problem 132.
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 1:
1
2
3
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2:
1
2
Input: s = "a"
Output: 0
Example 3:
1
2
Input: s = "ab"
Output: 1
Constraints:
- 1 <= s.length <= 2000
- s consists of lower-case English letters only.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
int minCut(string s) {
int len = s.size();
vector<vector<int>> dp(len, vector<int>(len, 1));
for (int i = 0; i < len; i ++) {
for (int j = i-1; j >= 0; j --) {
if (s[i] != s[j])
dp[j][i] = 0;
if (!dp[j+1][i-1])
dp[j][i] = 0;
}
}
vector<int> cut(len, INT_MAX);
for (int i = 0; i < len; i ++) {
for (int j = 0; j < i+1; j ++) {
if (dp[j][i]) {
if (j != 0)
cut[i] = min(cut[i], cut[j-1]+1);
else
cut[i] = min(cut[i], 0);
}
}
}
return cut[len-1];
}
};