I_lOVE_ROMAN's blog

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

»
6 weeks 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
»
6 weeks 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
»
6 weeks 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