给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。
返回符合要求的 最少分割次数 。
示例:
输入:s = "aab"
输出:1
提示:
1 <= s.length <= 2000
s 仅由小写英文字母组成
这道题挺有意思的,和分隔回文串有点类似,但又有区别,这道题需要找到最小的分隔方案,且输入的串比较长,用分隔回文串中用到的每次检查是否是回文串时用到了双指针,在大规模输入时,这种方法并不好用,我们要用动态规划进行预处理,从而减少检查字符串是不是回文串的时间,这是第一点。第二,如何定义状态,设 f[n-1] 为长 n 的字符串分隔为回文串所需要的最小次数,那么如果前 n-1
个字符为回文串,那么,f[n-1] = f[n-2] + 1
,如果不是回文串,那么我们就要进行搜索,如果 0~i 为回文串,f[n-1] = f[i+1] + 1
,找到遍历所有的 i
使得 f[n-1]
最小,这样就完成整个算法。
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<int>> st(n, vector<int>(n));
for (int j = 0; j < n; ++j) {
for (int i = j; i >= 0; --i) {
if (i == j)
st[i][j] = true;
else if (j - i + 1 == 2) {
st[i][j] = (s[i] == s[j]);
}
else
st[i][j] = (s[i] == s[j]) && st[i+1][j-1];
}
}
vector<int> f(n);
for (int j = 1; j < n; ++j) {
if (st[0][j])
f[j] = 0;
else {
f[j] = f[j-1] + 1;
for (int i = 1; i < j; ++i) {
if (st[i][j])
f[j] = min(f[j], f[i-1]+1);
}
}
}
return f[n-1];
}
};
联系客服