[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)


       class Solution {
            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++){
                            dp[j][i]=(s[i]==s[j]) && dp[j+1][i-1];
                            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.


      class Solution {
            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 times AC solution

    class Solution {
        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]);
                        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.