[recommend for beginners]clean C++ implementation


  • -1

    the first version implementation

    the key idea is to calculate the cut[i], and of course, at first, I want to use

       dp[i][j]  refers to the min-cut needed for s[i...j]  
       closed field  s[i,j]
    

    But I failed to figure out how to write the implementable equations.

    So I referred to the top voted post. As you can see,
    They set that

      cut[i] refers to the min-cut needed for s[0..i-1]
      open  filed s[0,i) means s[0, i-1]
    

    So the equation would be like this

      cut[i] = min{ cut[j]+1 if s[j...i] is palindrome }   s.t.  j<=i
    

    The coding key points is as :

     -1- inilize the cut[i] = i-1;
    
     -2- when dp[i][j]  we can update the  cut[i] = min(cut[i], cut[j]+1)
    

    Code

       class Solution {
        public:
            int minCut(string s) {
                /*** 
                 *  cut[i] = min{ cut[j] + 1 } 
                 *      s.t. dp[j][i]=true which means s[j..i ] is palindrome
                 *           cut[i] means the min-cut needed for s[0...i]
                 ***/
                int len=s.size();
                vector<vector<bool>> dp(len, vector<bool>(len, false));
                vector<int> cut(len+1);
                for(int i=0; i<len; i++)   dp[i][i]=true;
                for(int i=0; i<=len; i++)  cut[i]=i-1;
                
                for(int i=0; i<len; i++){
                    for(int j=0; j<=i; j++){
                        if(i-j<=1) 
                            dp[j][i]=(s[i]==s[j]);
                        else
                            dp[j][i]=(s[i]==s[j]) && dp[j+1][i-1];
                        if(dp[j][i])
                            cut[i+1]=min(cut[i+1], cut[j]+1);
                    }
                }
                return cut[len];
            }
        };

  • 1

    In fact, I do think the most top-voted answer is too tricky. It is not easy to think and implement it with no bug. I do think almost non-of-the-voters can implement it with out looking at this post. I do think the key idea behind the implementation is that it want to save the palindrome check cost.

    So it just use loop to calculate the all-the-possible-palindrome-length and update the cut based on it.

    Code

      class Solution {
        public:
            int minCut(string s) {
                int n=s.size();
                vector<int> cut(n+1);
                for(int i=0; i<=n; i++)  cut[i]=i-1;
                for(int i=0; i<n; i++){
                    for(int j=0; i-j>=0&&i+j<n&&s[i-j]==s[i+j]; j++)
                        cut[i+j+1]=min(cut[i+j+1], 1+cut[i-j]);
                    for(int j=1; i-j+1>=0&&i+j<n&&s[i-j+1]==s[i+j]; j++)
                        cut[i+j+1]=min(cut[i+j+1], 1+cut[i-j+1]);
                }
                return cut[n];
            }
        };

  • 0
    2

    2 times AC solution

    class Solution {
    public:
        int minCut(string s) {
            int size_s = s.size();
            vector<vector<bool>> dp(size_s, vector<bool>(size_s, false));
            for(int i= 0; i < size_s; i++)  dp[i][i] = true;
            vector<int> cut(size_s + 1, 0);
            for(int i = 0; i <= size_s; i++)  cut[i] = i - 1;
            
            for(int i = 1; i < size_s; i++) {
                for(int j = 0; j <= i; j++){
                    if(i-j <= 1){
                        dp[j][i] = (s[j]==s[i]);
                    }
                    else{
                        dp[j][i] = (s[j]==s[i] && dp[j+1][i-1]);
                    }
    
                    if(dp[j][i]) {
                        cut[i+1] = min(cut[i+1], cut[j] + 1);
                    }
                }
            }
            return cut[size_s];
        }
    };

Log in to reply
 

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