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;elsedp[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;elsefor (int j = 1; j <= i; j++) {if (dp[i][j])f[i] = min(f[i], f[j - 1] + 1);}}return f[n - 1];}
};