TLE in STRMRG

jan18

#1

Kindly help me know why am I getting TLE in my solution.

Link to solution.

I have used LCS approach in my solution.

Thank You.


#2

Have you tried implementing the iterative version of the LCS instead of the recursive one you are using? That might help.


#3

See this solution. The reason is in C++, string object are passed to function as call by value unlike C string of character array which passed as call by reference. Hence every time the compiler allocate new memory for every recursion call and hence will lead to TLE.

As you can see in my solution, I have passed the string as call by reference and thus got AC


#4

I have seen that the iterative ones work but cannot understand why this one doesn’t.
I have used dp array to store results so that there is no repitition. Hence, this solution should have also worked!


#5

maybe the recursion depth goes so high that the system stack pop in and pop out takes time? (considering too many parameters?)


#6

Yes. Right. That maybe a reason.


#7

OK. Thank You.


#8

How do I write an iterative DP solution if I already know the recursive one?