My 12ms C++ DP O(n^2) time and O(n) space


  • 4
    C

    class Solution {
    public:

    int minCut(string s) {
        int ans = INT_MAX;
        bool why[s.size()];
        
        int t[s.size()+1];
        memset(t,0,sizeof(t));
        t[0]=-1;
        memset(why,0,sizeof(why));
        for(int i = 0;i< s.size();i++){
            int tmp = INT_MAX;
            for(int j = 0; j<=i;j++){
                if(j==i)
                    why[i] =true;
                else if(j == i-1)
                    why[j] = s[i-1] ==s[i];
                else
                    why[j] = (why[j+1]) &&(s[j] == s[i]);
                if(why[j]){
                    tmp = min(tmp,t[j]+1);
                }
            }
    
            
            t[i+1] = tmp;
        }
        return t[s.size()];
    }
    

    };


  • 0
    Y
    This post is deleted!

Log in to reply
 

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