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