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 ?