描述
给定字符串 s, 需要将它分割成一些子串, 使得每个子串都是回文串.
最少需要分割几次?
样例
样例 1:
输入: "a"
输出: 0
解释: "a" 本身就是回文串, 无需分割
样例 2:
输入: "aab"
输出: 1
解释: 将 "aab" 分割一次, 得到 "aa" 和 "b", 它们都是回文串.
思路：
考虑最后分割出来的是回文串的情况，加入最后分割出来的是回文串，那么前
个字符组成的字串最少的回文串分割数为
。为了降低运算复杂度，将
是回文串这一步的判断采用生成的方式实现。具体实现如下。
class Solution {
public:
/**
* @param s: A string
* @return: An integer
*/
int minCut(string &s) {
// write your code here
int n=s.size();
if(!n)
{
return 0;
}
vector<vector<bool>> isPalin(n,vector<bool>(n,false));
int l,r;
for(int i=0;i<n;i++)
{
l=r=i;
while(l>=0 && r<n && s[l]==s[r])
{
isPalin[l][r]=true;
l--;
r++;
}
l=i;
r=i+1;
while(l>=0 && r<n && s[l]==s[r])
{
isPalin[l][r]=true;
l--;
r++;
}
}
vector<int> dp(n+1,INT_MAX);
dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<i;j++)
{
if(isPalin[j][i-1])
{
dp[i]=min(dp[i],dp[j]+1);
}
}
}
return dp[n]-1;
}
};
