I usually am comfortable with memoization and I try to use that in every interview. Now that you explained clearly the DP solution, I am going to learn more about this. Thanks a lot.
Thanks for creating this! Really helped a lot! For the space optimised solution, how to find the LCS elements (like we traversed from the last to first cell in the grid)?
Whenever the character from both the strings is the same, we can add it to a buffer (Like StringBuilder in java, or char array in C++, etc.) - by the time we reach the end, it will have our LCS string value.
yes, you are right. You need all the entire matrix to backtrace but usually, the length is asked in the interviews. Check out the LeetCode and InterviewBit links that I have added. :)
@@KeertiPurswani Whenever the character from both the strings is the same, we can add it to a buffer (Like StringBuilder in java, or char array in C++, etc.) - by the time we reach the end, it will have our LCS string value.
One question if both strings are null isn’t that a common subsequence? Pls can someone clear this for me rest all I was able to understand but the first point is not clear.