Recursive only, memoization..


  • 0
    L
    map<pair<int,int>,bool > palmem;
    map<pair<int,int>, pair<int,int> > longmem;
    
    bool ispal( string &s, int i, int j)
    {
        pair<int,int> k(i,j);
        if( palmem.find(k) != palmem.end())
            return palmem[k];
            
        if( i>j ) return palmem[k]=true;
        if( s[i] != s[j]) return palmem[k]=false;
        else return palmem[k]=ispal(s, i+1, j-1);
    }
    
    
    pair<int,int> Recur_longpal(string &s, int i, int j) {
        
        pair<int,int> inp;
        if(longmem.find(inp) != longmem.end())
            return longmem[inp];
        
        if(ispal(s, i, j) )
            return longmem[inp]=inp;
        else if( i<j )
        {
            pair<int,int> max1,max2;
            max1=Recur_longpal(s,i,j-1);
            max2=Recur_longpal(s,i+1,j);
            
            if( (max1.second - max1.first) > max2.second - max2.first )
                return longmem[inp]=max1;
            return longmem[inp]=max2;
        }
    }
    
    string longestPalindrome(string s) {
        
        pair<int,int> m= Recur_longpal(s,0, s.length()-1);
        return s.substr(m.first, m.second - m.first+1);
            
    }

Log in to reply
 

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