题目描述

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",
Return1since the palindrome partitioning["aa","b"]could be produced using 1 cut.

看这题之前，先看一下

字符串分割为回文串（palindrome-partitioning-ii）

了解一下思路：

参考代码：

//利用rb-tree暂存已知的子串最小切割次数，不然就会超时
class Solution {
        map<string,int>mp;
public:
    int minCut(string s) {
        if(mp[s]>0) return mp[s];
        int minsum=0x3ffffff;
        int size=s.size();
        if(s.size()<=0) return 0;
        for(int i=1;i<=size;++i)
        {
            string word=s.substr(0,i);
            if(!judge(word)) continue;
            int partcut=0;
            if(s.substr(i).size()>0)
            {
                 partcut=minCut(s.substr(i));
                 mp[s.substr(i)]=partcut;
                 minsum=min(minsum,1+partcut);
            }
            else
                 minsum=0;
        }
        return minsum;
    }
private:
    bool judge(const string &str)
    {
        if(str.size()==0) return false;
        string rstr=string(str.rbegin(),str.rend());
        if(str==rstr) return true;
        else return false;
    }
};