首页 > 代码库 > leetcode Palindrome Partitioning II
leetcode Palindrome Partitioning II
Given a string s, partition s such that every substring of the partition is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
class Solution {public: int minCut(string s) { int len=s.length(); vector<int>f(len+1); vector<vector<bool>>d(len,vector<bool>(len)); for(int i=0; i<=len; i++) f[i]=len-1-i; for(int i=len-1; i>=0; i--){ for(int j=i; j<len; j++){ if(s[i]==s[j]&&(j-i<2||d[i+1][j-1])){ d[i][j]=true; f[i]=min(f[i],f[j+1]+1); } } } return f[0]; }};
分析：
1、f[i]表示区间 [i, n-1] 之间最小的 cut 数，初始值为每个字符简都需cut（不存在回文串情况）， n 为字符串长度，则状态转移方程为f (i ) = min {f (j + 1) + 1 } , i ≤ j < n
f[i]=min(f[i],f[j+1]+1); 中+1表示遇到回文串cut一次，再加上之后的cut数
2、回文串的处理：定义状态d[i][j]表示i到j间是否为回文，s[i]==s[j]&&(j-i<2||d[i+1][j-1])表示如果当前字符相同，并且上一状态为回文，则当前状态为回文。
leetcode Palindrome Partitioning II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。