首页 > 代码库 > Leetcode--Palindrome Partitioning II
Leetcode--Palindrome Partitioning II
Problem Description：
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.
For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.
cut[i] = min(cut[i]，1+cut[j] ) 0<=j<i
有个转移函数之后，一个问题出现了，就是如何判断[j,i]是否是回文？每次都从i到j比较一遍？太浪费了，这里也是一个DP问题。
定义函数
flag[i][j] = true if [i,j]为回文
那么
flag[i][j] = str[i] == str[j] && P[i+1][j-1];
class Solution {
public:
int minCut(string s) {
//if(s.size()==0)
// return 0;
int n=s.size();
vector<vector<int> > flag(n,vector<int>(n,0));
vector<int> cut(n+1);
for(int i=0;i<=n;i++)
cut[i]=i-1;
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
if(s[i]==s[j]&&(i-j<2||flag[j+1][i-1]==1))
{
flag[j][i]=1;
cut[i+1]=min(cut[i+1],cut[j]+1);
}
}
}
return cut[n];
}
};Leetcode--Palindrome Partitioning II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。