每日一练:分割回文串Ⅱ
LCR 094. 分割回文串 II - 力扣(LeetCode)
题目要求:
给定一个字符串 s
,请将 s
分割成一些子串,使每个子串都是回文串。
返回符合要求的 最少分割次数 。
示例 1:
输入:s = "aab" 输出:1 解释:只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2:
输入:s = "a" 输出:0
示例 3:
输入:s = "ab" 输出:1
提示:
1 <= s.length <= 2000
s
仅由小写英文字母组成
解法-1 动态规划 O(N):
这个题需要使用两个dp表,dp[i][j]存储以s[i]为结尾、s[j]为开头的字符串是不是回文;f[i]存储以s[0]开始、s[i]结尾的字符串全部分割成回文的最少分割次数。
先填写dp,方法和每日一练:回文子串-CSDN博客中一样。
然后填写f,f[i]有两种情况:
(1)[0,i]是回文,f[i] = 0;
(2)[0,i]不是回文,遍历j = [1,i],如果dp[i][j]==true,则f[i]=min(f[i],f[i-1]+1)。
class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<vector<bool>> dp(n);
for (int i = 0; i < n; i++)
dp[i].resize(i + 1);
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
if (s[i] == s[j]) {
if (i == j || j == i - 1)
dp[i][j] = true;
else
dp[i][j] = dp[i - 1][j + 1];
}
}
}
vector<int> f(n, n - 1);
f[0] = 0;
for (int i = 1; i < n; i++) {
if (dp[i][0])
f[i] = 0;
else
for (int j = 1; j <= i; j++) {
if (dp[i][j])
f[i] = min(f[i], f[j - 1] + 1);
}
}
return f[n - 1];
}
};
原文地址:https://blog.csdn.net/2303_78095330/article/details/142796832
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!