# LeetCode Palindrome Partitioning II

LeetCode 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.

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

```class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
for (int i = 0; i < n; i++)
dp[i][i] = true;
vector<int> cut(n, 0); // # of cut for s[0,j]
for (int j = 0; j < n; j++)
{
cut[j] = j; // set maximum # of cut
for (int i = 0; i <= j; i++)
{
if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1]))
{
dp[i][j] = true;

if (i > 0) // if need to cut, add 1 to the previous cut[i-1]
cut[j] = min(cut[j], cut[i - 1] + 1);
else // if [0...j] is palindrome, no need to cut
cut[j] = 0;
}
}

}
return cut[n - 1];
}
};
```

```.......aba...
|<-X->| ^
|<---Y-->|
```

```class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<int> cuts(n + 1, 0); // cuts[i] 表示前i个字符切成回文子串，最少的刀数
for(int i = 0; i <= n; ++i) cuts[i]  = i - 1;

for(int i = 0; i < n; ++i) {
for(int j = 0; i - j >= 0 && i + j < n && s[i - j] == s[i + j]; ++j) // 最后一个是奇数长回文子串
cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j] + 1);

for(int j = 1; i - j + 1 >= 0 && i + j < n && s[i - j + 1] == s[i + j]; ++j) // 最后一个是偶数长回文子串
cuts[i + j + 1] = min(cuts[i + j + 1], cuts[i - j + 1] + 1);
}
return cuts[n];
}
};
```