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.
动态规划题目，类似于矩阵链相乘。设dp[i][j]表示s[i,…,j]是否为回文串，cut[j]表示s[1,…,j]需要多少刀才能切成回文串。动态规划运行到最后返回cut[n]。
对于cut[j]，切第一刀的时候，我们尝试前面j个切割位点，比如我们尝试切第i点，则s[1,…,j]被分成了s[1,…,i-1]和s[i,…,j]，如果s[i,…,j]为回文串，则s[i,…,j]不需要再切了，又因为cut[i-1]我们之前已经算过了，所以在i处切一刀，有cut[j]=cut[i-1]+1。尝试所有的切割位点i，找最小的cut[j]。
如果发现i=1的时候s[i,…,j]为回文串，则s[1,…,j]不需要再切了，所以cut[j]=0。
完整代码如下：
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];
}
};本代码提交AC，用时84MS。
二刷。参考讨论区一个大神的做法：https://discuss.leetcode.com/topic/2840/my-solution-does-not-need-a-table-for-palindrome-is-it-right-it-uses-only-o-n-space。这种方法不需要上面的做法的dp数组，效率也会高很多。
还是需要cuts数组，cuts[i]表示前i个字符切成回文子串，最少的刀数。对于每一个字符，我们枚举以该字符为中心，能够扩展到的最长的回文子串的长度，比如下图，以b为中心扩展，扩展到aba是一个回文子串，那么要把Y切成回文子串，需要的刀数不超过把X切成回文子串需要的刀数加1，也就是cuts[Y]=min(cuts[Y],cuts[X]+1)。
注意，扩展的时候，需要考虑到以b为中心的回文子串的长度是奇数还是偶数。
.......aba... |<-X->| ^ |<---Y-->|
通过枚举每一个回文中心点，我们可以算到所有的cuts，最后返回cuts[n]。完整代码如下：
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];
}
};本代码提交AC，用时6MS，神速。
三刷。两个DP，第一个DP求解出任意两个位置的子串[i:j]是否为回文。第二个DP2，DP2[j]表示前j长的字符串，需要的最小cut数，对于第j个字符，它可以自己独立成为一个回文，所以DP2[j]=DP2[j-1]+1；还可以遍历j前面的字符i，如果[i:j]能形成回文的话，则DP2[j]=DP2[i-1]+1。完整代码如下：
class Solution {
public:
void preprocess(const string &s, vector<vector<int>> &dp) {
int n = s.size();
for (int i = 0; i < n; ++i)dp[i][i] = 1;
for (int len = 2; len <= n; ++len) {
for (int i = 0; i < n; ++i) {
int j = i + len - 1;
if (j < n && s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
dp[i][j] = 1;
}
}
}
}
int minCut(string s) {
int n = s.size();
if (n == 0 || n == 1)return 0;
vector<vector<int>> dp(n, vector<int>(n, 0));
preprocess(s, dp);
vector<int> dp2(n, 0);
for (int j = 1; j < n; ++j) {
dp2[j] = dp2[j - 1] + 1;
for (int i = j - 1; i >= 0; --i) {
if (dp[i][j] == 1) {
int pre_cut = i > 0 ? dp2[i - 1] + 1 : 0;
dp2[j] = min(dp2[j], pre_cut);
}
}
}
return dp2[n - 1];
}
};本代码提交AC，用时44MS。