132 - 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.

Hide Tags

Dynamic Programming

Hide Similar Problems

(M) Palindrome Partitioning

照猫画虎把 Palindrome Partitioning 的代码拿来改了改提交断然是超时…，看来提示 DP 是有原因的。
没怎么想出 DP 怎么递推，只好去查帖子。
虽然讲这道题的帖子不少，但好多都是聊聊数语一笔带过，看来看去总觉得理解不是很透彻。

后来遇到这个帖子，基本上理解清楚了：
核心的思想是用一个一维数组来记录从开始到每个字符所需要切的最小刀数，初始化为字符的下标（也就是最大可能的刀数）
然后利用二维矩阵来判断子串 s[substr_start, substr_end] 是不是一个回文（下图蓝色的两个格子之间，含它们），
如果是，那么就可以在 substr_start 之前切一刀（红色的线），
而在子串 s[substr_start, substr_end] 中就不用再切了，这样就能减少切的刀数，
因此在 substr_end 的位置，最小刀数是在 （substr_start-1  里存的刀数 + 1）与自己已经存了的刀数之间取更小的那个。
如果不是，则无需处理。
这样当通过 substr_start, substr_end 的移动检测过所有的子串之后，从开始到每个字符的最小刀数也就都有了，
最后的结果就是一位数组里最后的一个值了。

在写代码的时候，跟原帖稍有不同的是，它填的是二维矩阵的上半部分，我填的是下半部分，依赖的方向不一样
具体的不同之处在之前的 005 - Longest Palindromic Substring 的 DP 再分析 里分析过了，一个是垂直填，一个是水平填。

另外就是二维数组一开始用的 int 型的，但是当字符串长度大于一定值的时候，这个数组的大小就超过了默认栈的大小，
直接导致栈溢出，runtime error，（有个 case 有 1462个字符，算算都超过 8M 了）改成 bool 型之后就没有问题了。

 

class Solution {
public:
    int minCut(string s) {
        int len=s.length(), p1=0, p2=len-1;
        if(!len || 1==len)              //special cases: empty/single character
            return 0;

        bool mtx[len][len];             //"int" array might be bigger than the stack size for long strings
        int  min_cut[len];              //store minimal cut number for substr s[0 ~ current character]
        for(int substr_end=0; substr_end<len; ++substr_end)
        {
            //pre-set max cut number for each substr end node
            min_cut[substr_end] = substr_end;
           
            //check each substr start node from 0~substr_end for possible smallest cut number
            for(int substr_start=0; substr_start<=substr_end; ++substr_start)
            {
                //initialize as substr is not palindrome
                mtx[substr_end][substr_start] = false;
               
                //only update min_cut if substr s[substr_start, substr_end] is palindrome:
                if(s[substr_start]==s[substr_end] &&                    //characters are equal
                    (1>=substr_end-substr_start ||                      //same or adjacent character
                        mtx[substr_end-1][substr_start+1]))             //other cases: rely on Right-Up
                {
                    //mark as is palindrome for future relying
                    mtx[substr_end][substr_start] = true;
                   
                    //if substr s[0~substr_end] is palindrome we don't need cut it.
                    if(!substr_start)
                        min_cut[substr_end] = 0;
                    //if need one more cut for substr s[substr_start~substr_end],
                    //then add 1 to previous smallest cut number before substr s[substr_start~substr_end]
                    //which is the number stored in min_cut[substr_start-1]
                    else
                        min_cut[substr_end] = min(min_cut[substr_end], min_cut[substr_start-1]+1);
                }
            }
        }
        return min_cut[len-1];
    }
};
24 ms.