Longest Common Subsequence - Leetcode 1143 - Dynamic Programming (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@breepoken4218]

In some ways i find you better than neetcode and other mainstream ones. Underrated and keep uploading!!

[@GregHogg]

That's what I like to hear 😊

[@ashwanigaur1828]

Yes agreed..

[@thotapraveenvlogs7020]

Super

[@MegaBeastro]

great video. I think what helped me visualize the 2d array solution was viewing the empty string as first row and column instead of the first characters of the strings

[@jenex5608]

Better than neetcode in my opinion

[@siddharthpradeep]

Your Videos really help me learn better. Keep uploading man !

[@GregHogg]

Glad to hear it, will do!

[@Here.s_how]

can't we do it using memoization? my code runtime error

[@KandadaiSrinivasaManohar]

So which is best , top down or bottom up approach?

[@Beeram123]

This is Great video explaination of the Longest Common Subsequence problem!!BTW what are you using whiteboard drawings ?

[@GregHogg]

Thank you so much! And it's called Miro :)

[@nice-vf4rj]

Hi Greg can you do string compression? Thanks in advance!!

[@SemesterAtSeaHopeful]

If the recursive solution and the tabulation have the same time complexity, why is the tabulation so much faster?

[@Ambatakummmmm]

iteration is usually a lot faster than recursion

[@Redaxi]

Time complexity does not mean runtime, it simply shows how fast runtime gets bigger with respect to the input length

[@shun6284]

I feel so noob, I can't come up with this solution on my own 😢

[@GarouNguyen]

bro it top left approach to bottom, why you call this bottom uo

[@GregHogg]

Bottom = base cases, top = n (what you desire)

[@Martinnnnnn-e5s]

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 😂

[@SwizzRizzBizz]

how are supposed to solve questions like these in an interview in a matter of minutes? These companies are just insane

[@GarouNguyen]

dp i j = dp i-1 j, dp i j-1 can you explain bro, i still don't unserstand

[@Martinnnnnn-e5s]

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

[@adithyar3160]

you baller...❤

[@GregHogg]

🏀

[@fantastic-b2m]

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

[@iancdp9]

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.