I_lOVE_ROMAN's blog

Leetcode dp Problem
By I_lOVE_ROMAN, history, 7 days 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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

use expand from middle technique, at each index maintain two pointers left and right, and keep moving them those in opposite direction till they maintain the condition of palindrome, and keep updating the longest substring if you find a longer one.

→ Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

You can define $$$dp[i][j]$$$ where $$$i \le j + 1$$$ as $$$true$$$ if the substring $$$i..j$$$ is a palindrome and $$$false$$$ otherwise. Base cases are: the substring $$$j + 1..j$$$ represents an empty string, so it is always $$$true$$$. The substring $$$i..i$$$ is always a palindrome, too. Transition is $$$dp[i][j]$$$ is $$$true$$$ if $$$s[i] == s[j]$$$ $$$AND$$$ $$$dp[i + 1][j - 1]$$$. Otherwise, it is $$$false$$$.

→ Reply
  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I want to know why it is getting MLE.Can you explain that ?

    → Reply
»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

try bool checkPalindrome(int l,int r,string& s, vector<vector>& dp) instead of bool checkPalindrome(int l,int r,string s, vector<vector>& dp)

→ Reply