LeetCode 132. 分割回文串 II（DP）
LeetCode 132. 分割回文串 II（DP）
Michael阿明
发布于 2021-02-19 09:43:27
发布于 2021-02-19 09:43:27
文章被收录于专栏：Michael阿明学习之路
文章目录
1. 题目
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-partitioning-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
dp[i]表示到 i 为止的子串最少需要分割多少次- 如果一个子串为回文串，dpi = 0
- 如果不是，遍历所有的 j （j <= i）,
如果s[j,i]是回文串，dp[i] = min(dp[i], dp[j-1]+1)
28 / 29 个通过测试用例
# 超时例子
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"class Solution {
public:
int minCut(string s) {
int i,j,n = s.size();
vector<int> dp(n,0);
if(s.size()<=1)
return 0;
for(i = 0; i < n; ++i)
dp[i] = i;
for(i = 1; i < n; ++i)
{
for(j = i; j > 0; --j)
{
if(ispalindrome(s,0,i))
dp[i] = 0;
else if(ispalindrome(s, j, i))
dp[i] = min(dp[i], dp[j-1]+1);
}
}
return dp[n-1];
}
bool ispalindrome(string& s, int l, int r)
{
while(l < r)
{
if(s[l++]!=s[r--])
return false;
}
return true;
}
};- 预先预处理得到所有可能的区间是否是是回文串
- 参考：LeetCode 5. 最长回文子串（动态规划）
class Solution {
public:
int minCut(string s) {
int i,j,len,n = s.size();
vector<int> dp(n,0);
vector<vector<bool>> ispalind(n,vector<bool>(n,false));
if(s.size()<=1)
return 0;
for(i = 0; i < n; ++i)
{
dp[i] = i;
ispalind[i][i] = true;
if(i < n-1 && s[i]==s[i+1])
ispalind[i][i+1] = true;
}
for(len = 1; len < n; ++len)
{
for(i = 0; i < n-len; ++i)
{
if(ispalind[i][i+len-1] && i-1>=0 && s[i-1]==s[i+len])//是回文串
ispalind[i-1][i+len] = true;
}
}
for(i = 1; i < n; ++i)
{
for(j = i; j > 0; --j)
{
if(ispalind[0][i])
dp[i] = 0;
else if(ispalind[j][i])
dp[i] = min(dp[i], dp[j-1]+1);
}
}
return dp[n-1];
}
};124 ms 7.4 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/07/11 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
