Longest Common Subsequence - Dynamic Programming - Leetcode 1143

0:00 - Read the problem
4:23 - Read the problem
14:05 - Read the problem

leetcode 1143

#sorted #array #python

[thecomputerman]

Damn, I looked at the problem from your list of 75 problems as I am preparing for an interview, the first time I looked at the problem, I went black, I had a 15 minute timer, I just didn't know what to do and how to proceed. not even close. never could comprehend that a 2D matrix could be a way to look at problems like that, You just opened up my thought process.

I have more than 10+ years of experience but I never attempted competitive programming (I'm from a systems engineering background (devops/sre sort) and never required these sorts of problems to be solved, neither in real life nor in any interview).

Thanks a ton, Dude for all your efforts. Really appreciate it.

[paulreilley]

I didn't understand this concept until you explained it. As an educator I can confidently say fantastic job!

I'm working on this concept on Codecademy and it took me a minute to realize that you set the no character columns as bottom and right, whereas Codecademy does them as left and top. Seeing it done both ways and the subtle differences in the code was extremely helpful to fully comprehend the purpose of this exercise. Thank you!

[alokesh]

Great solution, as always, but even if you solve this starting at the first cell of the table, it would still be a bottom-up approach. Tabulation is called bottom-up because we are starting from a smaller problem and we are building up to the larger problem's solution.
Memoization is called a top-down approach because we start from the larger problem and break into smaller problems using recursion (something like recursiveFunction(n - 1)).

So, basically, tabulation DP, which is what is done here, is bottom-up.
Memoization DP is top-down.

[sajinkowser]

From trivial questions to niche ones, every single video is quality – great stuff man!

[albertd]

We could use a full-size 2d grid, but all we really need it 2 rows with the length of the x-axis, in this case, text2.

- Time complexity: O(len(text1) * len(text2))
- Space complexity: O(len(text2))

class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
prevRow = [0] * (len(text2) + 1)

for r in range(len(text1) - 1, -1, -1):
curRow = [0] * (len(text2) + 1)
for c in range(len(text2) - 1, -1, -1):
if text1[r] == text2[c]:
curRow[c] = prevRow[c + 1] + 1
else:
curRow[c] = max(curRow[c + 1], prevRow[c])
prevRow = curRow

return prevRow[0]

[ku-]

Thanks for the explanation. It has been exremely helpful as usual!!

Note to others: when initialising dp in the beginning, doing dp = [[0] * (len(text2) + 1)] * (len(text1) + 1) does NOT work because this creates "len(text1) + 1" number of REFERENCES, so updating one array will update everything else. You can try and print the dp array and see for yourself. I found this explanation from the LC discuss section, and didn't realise this in my solution and I was stumped on why my answer was incorrect!

[fatbubble]

This is the most incredible explanation of 2D Dynamic Programing solutions I have ever seen.

Props to NeetCode for that *Fantastic* visual representation

[amardeepbhowmick]

Your channel has the best content on Dynamic Programming, both from the theory as well as the coding perspective!

[jonaskhanwald]

Bro please upload videos daily. I'm very dependent on you. Your videos are the best to understand.

[srinadhp]

Wow! That is something! Had to watch couple of times to understand the very difficult concept.. but as usual, you made it so simmple with your impeccable explanation. Amazing stuff! Thanks a lot!

[PC-prgi]

you make it look so SIMPLE !!! In fact after the visualization/explanation, the code just comes naturally to one's mind.

[josecabrera]

dude, I never write comments but thank you !!! I hope you know that you have made an impact on several people's lives for the better.

[kevincai]

My favorite channel on youtube!!! Thanks a lot for the great work, it helps me so much!
Continue to solve more leetcode problems and help more people to understand it.

[julesrules]

I've watched a bunch of videos to understand this question, and this one is by far the most intuitive to me. I can't thank you enough. 👏👏👏👏👏

[kunal_chand]

The best visual explanation for this problem. I finally understand why do we take the 2D DP array. Because every cell in the array holds information to compare every possible subsequence

[iamdeancoulstock]

Genius solution. Took 3-4 replays to fully grasp, but I feel great about it now. Thanks for your work!

[ukuduck]

Couldn't appreciate more, really. My daily routine is basically, continue watching your 75 question playlist, try to solve the problem by myself, then watch your brilliant explanation no matter if I pass it or not. I just completed this 2D DP problem, which I previously feared I couldn't think it through, without watching your code. This feels so good! Simply, thank you!!

[thankgodukachukwu]

There's an important thing to note in solving this problem using bottom up (used here) or top down tabulation approach. Understand that the shorter text has to be the length of the row while the longer text has to be the length of the cols. So in the example, text2 becomes n and text2 m so you can have a nxm mutidimentional array. With this and the excellent explanation here, you can ace this problem in any interview and also show that you understand it making your knowledge of DP better. And also makes you a better programmer.

[luis-azanza]

I love the way you explain complicated problems like this one. There's just some many different approaches!
Thank you so much :)

[berke-ozgen]

I feel like there is a light at the end of the tunnel! One of the most clear explanation I have ever vitnessed. Thanks mate!