if they don't match, you want to go one step backwards, so the current LCS is the same as one step before. Either "i" "j" can go back, so we want the max of them
I tried to do it like Longest Increasing Subsequence. I see string 2 as an indicator of whether I can add the current letter to the subsequence in string 1. However, there might be repetitive letters and it's all too complicated to make it work so I gave up 😂
Master Data Structures & Algorithms For FREE at AlgoMap.io!
If the recursive solution and the tabulation have the same time complexity, why is the tabulation so much faster?
Your Videos really help me learn better. Keep uploading man !
Glad to hear it, will do!
In some ways i find you better than neetcode and other mainstream ones. Underrated and keep uploading!!
That's what I like to hear 😊
Yes agreed..
Super
This is Great video explaination of the Longest Common Subsequence problem!!BTW what are you using whiteboard drawings ?
Thank you so much! And it's called Miro :)
I feel so noob, I can't come up with this solution on my own 😢
bro it top left approach to bottom, why you call this bottom uo
Bottom = base cases, top = n (what you desire)
dp i j = dp i-1 j, dp i j-1 can you explain bro, i still don't unserstand
if they don't match, you want to go one step backwards, so the current LCS is the same as one step before. Either "i" "j" can go back, so we want the max of them
how are supposed to solve questions like these in an interview in a matter of minutes? These companies are just insane
I tried to do it like Longest Increasing Subsequence. I see string 2 as an indicator of whether I can add the current letter to the subsequence in string 1. However, there might be repetitive letters and it's all too complicated to make it work so I gave up 😂
you baller...❤
🏀
Hi Greg can you do string compression? Thanks in advance!!
So which is best , top down or bottom up approach?
am i having some misunderstanding here? the chart that i calculated myself with the same input is
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 2
0 1 1 2 2 2
0 1 1 2 2 2
0 1 1 2 3 3
0 1 1 2 3 4
That's right, I'm having the same output as you, I believe Greg omitted "a"' from each strings which is why it's still 1 and not 2 in his table.