Recursive only, memoization..

  • 0
    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;
            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.