Sharing my C++ solution


  • 0
    T
    class Solution {
    
    public:
        int minCut(string s) {
            int n = s.length();
            if(n<2)
                return 0;
            char str[n+1];
            strcpy(str, s.c_str());
            
            vector<vector<bool>> DP;
            DP.resize(n);
            int i, j;
            for(i=0; i<n; i++)
                DP[i].resize(n, false);
                
            for(i=0; i<n; i++)
                DP[i][i] = true;
            /*for(i=1; i<n; i++)
                DP[i-1][i] = true;*/
                
            int len;
            int start, end;
            for(len=2; len<=n; len++)
                for(i=0; i<=n-len; i++)
                    {
                        start = i;
                        end = i+len-1;
                        if((start+1) > (end-1))
                            DP[start][end] = (str[start] == str[end]);
                        else
                            DP[start][end] = ( (DP[start+1][end-1]) && (str[start] == str[end]) );
                    }
    
            vector<int> minCutDP(n+1, 0);
            for(i=0; i<=n; i++)
                minCutDP[i] = i-1;
                
            for(j=1; j<n; j++)
                for(i=j; i>=0; i--)
                {
                   if(str[j] == str[i] && ((i+1)>(j-1) || DP[i+1][j-1]))
                       minCutDP[j+1] = min(minCutDP[j+1], 1+minCutDP[i]);
                }
                
            return minCutDP[n];
        }
    };

Log in to reply
 

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