Share my thoughts and solution.


  • 0

    The laziest idea is backtracking, but obviously, there are too many duplicates. And the duplicates come from the process we check if the sub-string is palindrome. So the first idea is saving all of the start-end index of each palindrome into a grid. But how to build this graph?

    1. Scan from the two ends to the center?

    2. start from a point and spread forward and backward?

    We should take the second method because the palindrome grows from one to multi. If you take the first method, then in most of cases you will fail to find one.

    After build this DAG, it becomes a typical DP problem:

    • d(j) = min( d(j), d(i)+1 ), if the palindrome starts from i and ends at j.

    So the code is:

    class Solution {
    public:
    int minCut(string s) {
        int len=s.length();
        if(len==0) return 0;
        vector<vector<int>> g(len, vector<int>(len+1, 0));
        for(int i=0; i<len; ++i){
            int left=i;
            int right=i;
            while(right<len && s[left]==s[right]) {
                g[left][++right]=1;
            }
            --left;
            while(left>=0 && right<len && s[left]==s[right]){
                g[left--][++right]=1;
            }
        }
        vector<int> d(len+1, INT_MAX);
        d[0]=0;
        for(int i=0; i<len; ++i){
            for(int j=i+1; j<=len; ++j){
                if(g[i][j]){
                    d[j]=min(d[i]+1, d[j]);
                }
            }
        }
        return d[len]-1;
    }};
    

    But, if we look at the code again and might find that the graph is useless because we only assign the value when g[i][j] is true. So just keep the assignment of d[j], and delete the code of the graph. That should work, too.

    class Solution {
    public:
    int minCut(string s) {
        int len=s.length();
        vector<int> d(len+1, INT_MAX);
        d[0]=0;
        for(int i=0; i<len; ++i){
            int left=i;
            int right=i;
            while(right<len && s[left]==s[right]) {
                ++right;
                d[right]=min(d[left]+1, d[right]);
            }
            --left;
            while(left>=0 && right<len && s[left]==s[right]){
                ++right;
                d[right]=min(d[left--]+1, d[right]);
            }
        }
        return d[len]-1;
    }};

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.