描述

给定字符串 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;
    }
};