题目描述
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
算法1
这题同上一题131 分割回文串比较类似,但是在时间上要求更高
同样的 我们使用dp[i][j]表示 字符串i到j是否是回文字符串
但是即使我们有了这样的dp数组,如果使用dfs去尝试各种分割回文字符串的组合,依旧会超时tle
我们可以发现 1~n的字符串中 如何切割最小次数的回文字符串 其实是依赖于前面 1~n-1 ,1~n-2等子字符串的切割方案的 ,
而且1~n的字符串切割方案是不影响前面的切割方案的结果。 我们依旧尝试使用dp 。
我们就是根据K能和前面字符串组成回文的组合(查询dp) 计算出最小切割数即可
代码如下
C++ 代码
class Solution {
public:
vector<vector<int>> dp;
int ans = 9999999;
void initDp(const string& s)
{ //计算dp[i][j] 字符串s的i到j的子字符串是否是回文
dp = vector<vector<int>>(s.size() + 10, vector<int>(s.size() + 10));
for (int i = 0; i < s.size(); i++) { dp[i][i] = 1; }
for (int i = 0; i < s.size() - 1; i++) {
int l = i - 1; int r = i + 1;
while (l >= 0 && r < s.size() && s[l] == s[r]) {
dp[l][r] = 1; l--; r++;
}
l = i - 1; r = i + 2;
if (s[i] == s[i + 1]) dp[i][i + 1] = 1;
while (l >= 0 && r < s.size() && s[l] == s[r] && s[i] == s[i + 1]) {
dp[i][i + 1] = 1;
dp[l][r] = 1; l--; r++;
}
}
}
int minCut(string s) {
initDp(s);
int count[2000]; memset(count, 0x3f, sizeof count);
count[0] = 0; //每次新加入的字符串和前面的字符能否组成回文,如果可以 计算下当前的最小切割数
for (int i = 1; i < s.size(); i++) {
count[i] = count[i - 1] + 1;
for (int j = i-1; j >= 0; j--) {
if (dp[j][i] == 1 && j != 0) {
count[i] = min(count[i], count[j-1]+1);
}
else if (dp[j][i] == 1 && j == 0) {
count[i] = 0;
}
}
}
return count[s.size()-1];
}
};