[LeetCode]132.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.

思路

此题可以用动态规划求解。isPal[j][i]表示字符串s的子串s[j…i]是否为回文串，cut[i]表示子串s[0…i]所需要的最小分割数

代码

    /**------------------------------------
    *   日期：2015-03-02
    *   作者：SJF0115
    *   题目: 132.Palindrome Partitioning II
    *   网址：https://oj.leetcode.com/problems/palindrome-partitioning-ii/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include <iostream>
    #include <vector>
    #include <cstring>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        int minCut(string s) {
            int size = s.size();
            if(size == 0){
                return 0;
            }//if
            // isPal[i][j]表示字符串s的子串s[i,j]是否为回文串
            bool isPal[size][size];
            memset(isPal,0,sizeof(isPal));
            // cut[j]表示子串s[0,j]所需要的最小分割数
            int cut[size];
            // cut[0,i]
            for(int i = 0;i < size;++i){
                // [0,i]最多分割i次
                cut[i] = i;
                // 判断s[j,i]是否是回文串
                for(int j = 0;j <= i;++j){
                    // s[j,i]是回文串
                    if(s[j] == s[i] && (i - j <= 1 || isPal[j+1][i-1])){
                        isPal[j][i] = true;
                        // s[0,i]是回文串
                        if(j == 0){
                            cut[i] = 0;
                        }//if
                        else{
                            cut[i] = min(cut[i],cut[j-1]+1);
                        }//else
                    }//if
                }//for
            }//for
            return cut[size-1];
        }
    };

    int main(){
        Solution s;
        string str("cabababcbc");
        cout<<s.minCut(str)<<endl;
        return 0;
    }

运行时间