Getting Time Limit Exceeded Error

#1

I am trying to solve this DP question from leetcode.
516. Longest Palindromic Subsequence
I have used Top-Down Approch i.e, recursion+memoization.
I have done the memoziation as much as possible.
Then also i am getting TLE.
Now my doubt is, is there any bug in my code… Or this problem can’t be solved by top-down approch.
This is My code…


Thanks

#2

Hey @ashishnnnnn
Please explain u approach :slight_smile:

#3

First i created another string which is the reverse of the given string.
Now after that i tried to find Longest common subsequence (LCS) in the both string.
To find LCS i have used Recursion+Memoization,
Now if for given (i,j) which is index if string one and string two, if there is no memoized solution exists then we calculate the solution for that (i,j) and while calculating solution of (i,j) here we don’t assume that solution of (i+1,j+1) ,(i,j+1) or (i+1,j) doesn’t exist.
First we check if the solution of (i+1,j+1) ,(i,j+1) or (i+1,j) exists then we don’t calulate the solution for them, otherwise we do the solution calculation for (i+1,j+1),(i+1,j) or (i,j+1).
Now at last we return the length of LCS.
This is my approch…

#4

Hey @ashishnnnnn
Pass string by reference instead of copy ,that is what taking extra time

int solve(string &text1,string &text2,int i,int j,int l1,int l2,int arr[][1001]){

#5

Yes… It was the same problem.
But could you explain in some detail, why is it happening so…

#6

When u pass by value for each recursion call string is copied, there will be around 10^6/2 recursion calls in worst case
and 10^3 length string will be copied that many ties leading to TLE