【leetcode】Palindrome Partitioning II

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.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

 
采用动态规划的方法
首先可以先得到isP[i][j],即字符串中,从i到j是否是回文
isP[i][j]=((s[i]==s[j])&&(j-i<=1||isP[i+1][j-1]))
然后我们再确定分割次数
 
dp[i]代表了从i到n的最小分割次数,只需要从中间找到一点,使得分割次数最少即可
dp[i]=min(dp[k]+1)   k=i+1……n
 
 class Solution {
public:
int minCut(string s) { int n=s.length();
vector<vector<bool> > isP(n,vector<bool>(n,false)); for(int i=n-;i>=;i--)
{
for(int j=i;j<n;j++)
{
if(s[i]==s[j]&&(j-i<=||isP[i+][j-])) isP[i][j]=true;
}
} vector<int> dp(n+);
dp[n]=-; //注意边界条件,表示了dp[i]无需分割时,dp[i]=dp[n]+1=0;
for(int i=n-;i>=;i--)
{
int minCut=INT_MAX;
for(int k=i+;k<n+;k++)
{
if(isP[i][k-]&&minCut>dp[k]+)
{
dp[i]=dp[k]+;
minCut=dp[i];
}
}
} return dp[];
}
};
 
 
上一篇:安装Apache报80端口被占用 pid 4


下一篇:mod_rewrite模块详解