i was trying to solve this problemhttps://www.geeksforgeeks.org/printing-longest-common-subsequence/
but through a different process than what is explained here.
can anyone please tell me whether it is the correct solution for this problem?
this code is giving correct output for test cases which I have thought till now, but I wonder if it will be correct for all sorts of input
here is the code
https://ide.geeksforgeeks.org/G33GgLhp5W
Your implementation is fine, logically. It is doing exactly the same thing what the general approach is doing but storing the entire string at every position.
But i’d suggest not to follow this approach if string size is large.
Problem with this approach is since your dp state stores entire string. It would copy a string again and again in your dp[i][j] state. If you have to generate the string back. There’s one standard approach of traversing from N,M with a while loop and generating the string.
ooh okay thanks
means if the size of the string is 10^3 then it may cause TLE as the complexity may go up to 10^310^310^3 = 10^9
the last 10^3 refers to the copying of string at every dp[i][j].
isn’t it?