Блог пользователя I_lOVE_ROMAN

Автор I_lOVE_ROMAN, история, 8 дней назад, По-английски

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 ?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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$$$.

  • »
    »
    7 дней назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 дней назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)