江西哪里可以做企业网站,厦门做网站设计,漂亮logo图片,本地网站服务器搭建文章目录1. 题目2. 解题1. 题目
给定一个字符串 s#xff0c;将 s 分割成一些子串#xff0c;使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: aab
输出: 1
解释: 进行一次分割就可将 s 分割成 [aa,b] 这样两个回文…
文章目录1. 题目2. 解题1. 题目
给定一个字符串 s将 s 分割成一些子串使每个子串都是回文串。
返回符合要求的最少分割次数。
示例:
输入: aab
输出: 1
解释: 进行一次分割就可将 s 分割成 [aa,b] 这样两个回文子串。来源力扣LeetCode 链接https://leetcode-cn.com/problems/palindrome-partitioning-ii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dp[i]表示到 i 为止的子串最少需要分割多少次如果一个子串为回文串dp[i] 0如果不是遍历所有的 j j i,如果s[j,i]是回文串dp[i] min(dp[i], dp[j-1]1)
28 / 29 个通过测试用例
# 超时例子
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaclass Solution {
public:int minCut(string s) {int i,j,n s.size();vectorint 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();vectorint dp(n,0);vectorvectorbool ispalind(n,vectorbool(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[i1])ispalind[i][i1] true;}for(len 1; len n; len){for(i 0; i n-len; i){if(ispalind[i][ilen-1] i-10 s[i-1]s[ilen])//是回文串ispalind[i-1][ilen] 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 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
