Why this TLE despite memoization on palindrome checking and minCut?


  • 0
    L

    class Solution {
    public:

    bool ispal(string &str, int s, int e)
    {
        if(s>=e)
            return pal[s][e]=true;
        
        if( pal[s][e] != str.length() )
            return pal[s][e];
            
        return pal[s][e] = (str[s] == str[e] && ispal(str, s+1, e-1));
        
    }
    map<int,int> state;
    vector<vector<int> > pal;
    
    int minCut(string s)
    {
        state.clear();
        pal = vector<vector<int>>(s.length(),vector<int>(s.length(),s.length()));
        int d =minCut(s,0);
        return d;
        
    }
    int minCut(string s, int from) {
        
        if(state.find(from) != state.end())
            return state[from];
            
        if( ispal(s, from, s.length()-1))
            return state[from]=0;
        
        state[from]=s.length();
        for( int c=from; c<s.length(); c++)
        {
            if(ispal(s, from, c ) )
            {
                state[from] = min(state[from], 1+minCut(s, c+1) );
            }
        }
        return state[from];
    }
    

    };


Log in to reply
 

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