Problem Description

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.

Example 1

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2

Input: s = "a"
Output: 0

Example 3

Input: s = "ab"
Output: 1

Solution

Solution 1

This is a typical DP problem, we can use an one dimensional array dp[i] and define each sub-problem dp[i] as: the min cuts needed for the substring s[:i]. Next question is how to solve the sub-problem? We have to actually scan every s[j] with 0<=j<=i and ask whether s[j:i] is a palindrome, if it is, we need to update the dp array: dp[i] = dp[j-1] + 1. Note that we cannot update the array like: dp[i]=dp[j] since it's possible that within the j loop we only find a palindrome substring when j==i, in this case the expression dp[i]=dp[j] is invalid.

This is the general framework of solution. But the obvious question is how can we efficiently check whether a substring s[j:i] is a palindrome? We can of course brute force every substrings we needed to check, but it's apparently inefficient. It turns out we again can adopt the DP method to deal with this. This time we need to have a two dimensional array called isPal[i][j]. Every element isPal[i][j] indicates if the substring s[i:j] is a palindrome or not. We update isPal[i][j] = 1 when s[j]==[i] and dp[i-1][j+1]. Now we can code our programs as shown in the No.1 code.

Solution 2

As we mentioned in solution 1, the two dimension array is used to help us check if s[j:i] is a palindrome. Actually we can discard it when using Manchester method to check a palindrome string. The basic idea is to start from a char and grow the string on both sides by j chars with j>=0. We continue grow the string if the current string is a palindrome, and stop otherwise, then move to the next char and try growing again. This method is generally fast since a random s[i][j] is a palindrome with low probability. Thus this method can stop early to avoid testing more unnecessary strings. The remaining idea is the same as above: update dp array when we find a palindrome string. Details see code No. 2.

Solution 3

This method is from a different view: convert the problem into a graph problem and use the standard BFS to address the min cuts. In this graph, a node j is the neighbor of a node i when i and j are the two ends of a palindrome string. It's quite straightforward to think and implement the idea, but has slow speed and large memory request. Details see in code Bonus.

C++ Code, Number 1

 int minCut(string s) { // use two dimentional array isPal[i][j] to indicate whether (i,j) is a pal. And use one dimention array dp[i] to indicate the min cut needed for the string s[i:].
        int len = s.size();
        vector<vector<int> > isPal(len, vector<int>(len, 0));
        vector<int> dp(len);
        
        for(int i=len-1;i>=0;i--){
            dp[i] = len - 1 - i; // a baseline cut
            for(int j=i;j<len;j++){
                if(s[j]==s[i]){
                    if(j-i<2 || isPal[i+1][j-1]){
                        isPal[i][j] = 1;
                        if(j==len-1) dp[i] = 0;
                        else dp[i] = min( dp[i], dp[j+1]+1);
                    }
                }
            }
        }
        return dp[0];
        
    }

C++ Code, Number 2

// Manchester method to check a string is a pal or not, and no need to use two array anymore. dp here means the min cut needed for the string s[:i]
    int minCut(string s) {
        int len = s.size();
        vector<int> dp(len);
        for(int i=0;i<len;i++) dp[i] = i;
        for(int i=0;i<len;i++){
            for(int j=0; i-j>=0 && i+j<len && s[i-j]==s[i+j];j++){ // (i-j, i+j) is a pal, odd length
                if(i-j==0) dp[i+j] = 0;
                else dp[i+j] = min(dp[i+j], dp[i-j-1] + 1);
            }
            for(int j=0; i-j>=0 && i+j+1<len && s[i-j]==s[i+j+1];j++){ // (i-j, i+j+1) is a pal, even length
                if(i-j==0) dp[i+j+1] = 0;
                else dp[i+j+1] = min(dp[i+j+1], dp[i-j-1] + 1);
            }
            
        }
        return dp[len-1];
    }

C++ Code, Bonus

int minCut(string s) { // convert it to a graph first, and then do BFS
        int len = s.size(), ret = 0;
        if(len==0 || len==1) {return ret;}
        vector<set<int> > dp(len, set<int>()); // dp[i] is a set, an element j in this set means: (i,j) is a pal.
        for(int i=len-1;i>=0;i--){
            dp[i].insert(i); // one char is a palindrome itself
            for(int j=i+1;j<len;j++){
                if(s[j]==s[i]){
                    if(j==i+1 || dp[i+1].count(j-1)!=0) dp[i].insert(j);
                }
            }
        }
        
        // BFS on the dp, think of it as a graph
        set<int> frontier;
        frontier.insert(0);
        while(1){
            set<int> next;
            for(int num : frontier){
                for(int i : dp[num]){
                    if(i == len-1) return ret;
                    next.insert(i+1);
                }
            }
            frontier = next;
            ret ++;
        }
        return ret; // will not execute here
    }
文章目录