I_lOVE_ROMAN's blog

By I_lOVE_ROMAN, history, 2 hours ago, In English

Problem Statement :

Given a string s, return the longest palindromic substring in s.

My solution

class Solution {
public:
    
    
    
    bool checkPalindrome(int l,int r,string s, vector<vector<int>>& dp)
    {   
        
        //cout<<l<<' '<<r<<dp[l][r]<<endl;
        if(dp[l][r]==-1)
        {
            
            if(r-l<=1)
            {   
               
               //cout<<2<<endl;
                dp[l][r]= s[l]==s[r];
                return dp[l][r];
            }
            else 
            {   
                //cout<<3<<endl;
                bool is_palindrome=checkPalindrome(l+1,r-1,s,dp);
                
                dp[l][r]=s[l]==s[r] && is_palindrome;
                return dp[l][r];
            }
            
        }
        else 
        {
                return s[l]==s[r] && dp[l][r];
        }
        
    }
    string longestPalindrome(string s) {
               
               
               int n = s.size();
               vector<vector<int>> dp(n, vector<int>(n));
               int ans=-1,i,j;
               int curl=-1,curr=-1;

               for(i=0;i<n;i++)
               {
                for(j=0;j<n;j++)
                {
                    dp[i][j]=-1;
                }
               }

              // cout<<checkPalindrome(0,3,"aaca");
               for(i=0;i<s.size();i++)
               {
                for(j=i;j<s.size();j++)
                {   
                   //cout<<s.substr(i,abs(i-j)+1)<<' '<<checkPalindrome(i,j,s)<<endl;
                    if(checkPalindrome(i,j,s,dp) && abs(i-j)>ans)
                    {   
                        //cout<<s.substr(i,abs(i-j)+1)<<endl;
                        ans=abs(i-j);
                        curl=i;
                        curr=j;
                    }
               }

               }
                  //cout<<s.substr(curl,ans+1);
                return s.substr(curl,ans+1);

           //return s;
        
    }
};

It is getting MLE,my 2D vector is not a problem as the constraint is 10^3.

Is it for recursion stack ?

  • Vote: I like it
  • 0
  • Vote: I do not like it