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.

For example, given s = “aab”,
Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

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
/*
这里用到了两个dp,
一个是判断字符串s[i][j]是否为回文,
一个是记录s[0..i]最小的切割数
经典题
*/
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool> > isPal(n, vector<bool>(n, false));
vector<int> cut(n, 0);
for (int j = 0; j < n; j++) {
cut[j] = j;
for (int i = 0; i <= j; i++) {
//如果子串 s[i...j]是回文串
if (s[i] == s[j] && (j - i <= 1 || isPal[i + 1][j - 1])) {
isPal[i][j] = true;
if (i > 0)
cut[j] = min(cut[j], cut[i - 1] + 1);
else
cut[j] = 0; //如果 s[0...j]是回文串,则说明不需要切割
}
}
}
return cut[n - 1];
}
};