Longest Common Subsequence - Dynamic Programming - Leetcode 1143

แชร์
ฝัง
  • เผยแพร่เมื่อ 24 ธ.ค. 2024

ความคิดเห็น • 215

  • @NeetCode
    @NeetCode  3 ปีที่แล้ว +39

    🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤

    • @Qwantopides
      @Qwantopides ปีที่แล้ว +2

      Absolute legend! Recently I have been realizing how extremely helpful people in the competitive coding community are. Quite shocking to be honest. Like you! How much effort you have put in to help out others is amazing!

  • @thecomputerman1
    @thecomputerman1 2 ปีที่แล้ว +132

    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.

    • @audioplatform6299
      @audioplatform6299 8 หลายเดือนก่อน +6

      If the computer man cannot how can lesser mortals like some of us could😢?

    • @PhanNghia-fk5rv
      @PhanNghia-fk5rv 7 หลายเดือนก่อน +1

      Ty for ur sharing, i have an westion what bring u here to leetcode as u said that u dont need it for job

    • @chaitanyaswaroop7669
      @chaitanyaswaroop7669 6 หลายเดือนก่อน

      @@PhanNghia-fk5rv He said he never had any interviews or required to solve problems in the past. But as said in the first line, he is preparing for an interview now

  • @alokesh985
    @alokesh985 2 ปีที่แล้ว +120

    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.

    • @ashok2089
      @ashok2089 4 หลายเดือนก่อน

      Thanks!

    • @phantomcorn
      @phantomcorn 2 หลายเดือนก่อน

      It depends on what the 2d table represents right. I think from this video dp[i][j] represents the lcs of text1[i:] and text2[j:] so in this case starting from the first cell (dp[0][0]) would be a memoization.

  • @paulreilley5439
    @paulreilley5439 ปีที่แล้ว +10

    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!

  • @ku-1119
    @ku-1119 2 ปีที่แล้ว +23

    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!

    • @zactamzhermin1434
      @zactamzhermin1434 2 ปีที่แล้ว +3

      If you want to avoid double for loop list comprehension you can only do that in the inner loop so it should look like this instead:
      dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]

    • @itachid
      @itachid 2 ปีที่แล้ว

      Thank you. Was wondering the same.

    • @jahleelmurray2826
      @jahleelmurray2826 10 หลายเดือนก่อน

      Oh woww thank you man I was so perplexed 🤣

    • @quinnlangford6521
      @quinnlangford6521 5 หลายเดือนก่อน

      thanks for this

  • @albertd7658
    @albertd7658 ปีที่แล้ว +3

    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]

  • @sajinkowser7228
    @sajinkowser7228 3 ปีที่แล้ว +13

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

  • @josecabrera7947
    @josecabrera7947 2 ปีที่แล้ว +3

    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.

  • @amardeepbhowmick3614
    @amardeepbhowmick3614 3 ปีที่แล้ว +26

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

  • @fatbubble123
    @fatbubble123 2 ปีที่แล้ว +54

    This is the most incredible explanation of 2D Dynamic Programing solutions I have ever seen.
    Props to NeetCode for that *Fantastic* visual representation

  • @jonaskhanwald566
    @jonaskhanwald566 3 ปีที่แล้ว +211

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

    • @ritikajaiswal3824
      @ritikajaiswal3824 3 ปีที่แล้ว +6

      can you tell me whether watching the solutions helped you in doing good in DSA?

    • @varunshrivastava2706
      @varunshrivastava2706 2 ปีที่แล้ว +7

      @@ritikajaiswal3824 Try to solve the problem for 30min if you are unable to solve it then look for a video solution. Problem Solving is a skill that will take a lot of time to master!!!!

    • @balajivenkatraman2991
      @balajivenkatraman2991 2 ปีที่แล้ว +1

      @@ritikajaiswal3824 What an arrogant statement that is, we can do a math in our mind if it comes to algorithm certain formula/approach needed. Certainly his video helped me to improve a lot and able to apply the concept in other problems too.

    • @mohammadammech7934
      @mohammadammech7934 2 ปีที่แล้ว

      @@ritikajaiswal3824 it helped me a lot, in both DS and algorithms

  • @rohitkumaram
    @rohitkumaram 2 ปีที่แล้ว +6

    It is still your solution only:
    but I find normal iteration easier than reverse, it can depend person to person:
    dp = [[0 for j in range(len(text2)+1)] for i in range(len(text1)+1)]
    for i in range(1,len(text1)+1):
    for j in range(1,len(text2)+1):
    if text1[i-1]==text2[j-1]:
    dp[i][j] = 1 + dp[i-1][j-1]
    else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[len(text1)][len(text2)]

    • @NeetCode
      @NeetCode  2 ปีที่แล้ว +1

      Yeah, I'll probably do future problems with normal iteration

    • @rohitkumaram
      @rohitkumaram 2 ปีที่แล้ว +1

      @@NeetCode hey, you replied me thankyou so much would like to connect more. Since I want to become a faang engineer.

    • @CostaKazistov
      @CostaKazistov 2 ปีที่แล้ว

      💯agree - forward iteration is much easier to follow

    • @ritvikgaur3444
      @ritvikgaur3444 2 ปีที่แล้ว

      Hi Rohit , can you explain that why both for loop are not giving string index out of range error as we are doing (len(text1)+1) which will add extra 1 space at last which cannot be iterated at it is not defined.

    • @rohitkumaram
      @rohitkumaram 2 ปีที่แล้ว +1

      @@ritvikgaur3444 dp is defined with length +1,
      and while iterating string we are iterating always i-1, and j-1, so it will always be 1 less than last limit

  • @PC-pr8gi
    @PC-pr8gi 3 ปีที่แล้ว +6

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

  • @srinadhp
    @srinadhp 3 ปีที่แล้ว +42

    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!

  • @sashikshik
    @sashikshik 11 หลายเดือนก่อน +1

    RU: Меня просто угнетает тот факт, что я, не зная алгоритма более двух часов пытался решить эту задачу и не смог
    EN: I’m simply depressed by the fact that, without knowing the algorithm, I tried to solve this problem for more than two hours and could not

    • @issamjm3343
      @issamjm3343 22 วันที่ผ่านมา

      You shouldn't take that much time with a problem. If you didn't solve it within 45 minutes, it means that there is a trick that you don't know yet. If you want to progress fast, you should spend reasonable time with problems.

  • @samuelrobert2927
    @samuelrobert2927 หลายเดือนก่อน +1

    Do we really need to hold on to the entire matrix? an optimisation can be done for the space such that we compute row by row as the current value only dependence on the previous row and the right of the current row.

  • @thankgodukachukwu1168
    @thankgodukachukwu1168 หลายเดือนก่อน

    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.

  • @iamdeancoulstock
    @iamdeancoulstock หลายเดือนก่อน

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

  • @berke-ozgen
    @berke-ozgen 12 วันที่ผ่านมา

    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!

  • @kunal_chand
    @kunal_chand 2 ปีที่แล้ว

    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

  • @julesrules1
    @julesrules1 2 ปีที่แล้ว +2

    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. 👏👏👏👏👏

  • @danielsun716
    @danielsun716 2 ปีที่แล้ว +2

    FYI, I did a space compression. The memory complexity is O(n).
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    dp = [0] * (len(text2) + 1)
    for i in range(len(text1) - 1, -1, -1):
    nextDP = [0] * (len(text2) + 1)
    for j in range(len(text2) - 1, -1, -1):
    if text1[i] == text2[j]:
    nextDP[j] = 1 + dp[j + 1]
    else:
    nextDP[j] = max(dp[j], nextDP[j + 1])
    dp = nextDP
    return dp[0]

  • @thevagabond85yt
    @thevagabond85yt ปีที่แล้ว

    Since the problem is symmetric (solve start to end or end to start) you can also code a program which starts from 0th index... see this java code :
    class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
    int m= text1.length(), n= text2.length();
    int [][] match= new int[m+1][n+1];
    for(int i=0; i

  • @kevincai4249
    @kevincai4249 3 ปีที่แล้ว +5

    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.

  • @AlejandroRuiz-pd6ci
    @AlejandroRuiz-pd6ci 3 ปีที่แล้ว +2

    Dude NeetCode you are life savior, keep it up bro

  • @celbelle4182
    @celbelle4182 ปีที่แล้ว

    I am really struggling to wrap my head around coding, but your explanation was so engaging and simple. Thank you so much.

  • @snake1625b
    @snake1625b 2 ปีที่แล้ว +1

    wasnt expecting the code to be that short. amazing video btw, long your intuition in the beginning

  • @kaushiktd
    @kaushiktd 3 ปีที่แล้ว +2

    I have been struggling to get my mind around this until found this video. Thanks 🙏

  • @demaxl732
    @demaxl732 6 หลายเดือนก่อน

    you deserve everything this world has to offer

  • @dipesh1401
    @dipesh1401 3 ปีที่แล้ว +1

    this is the best video on this problem on yt

  • @hwang1607
    @hwang1607 ปีที่แล้ว +1

    i think this is easy to do after learning the solution but there was no way I would be able to figure out the solution myself

  • @bprincepandey
    @bprincepandey 2 ปีที่แล้ว +1

    The best explanation of LCS I have seen. Thanks man.

  • @raminessalat9803
    @raminessalat9803 ปีที่แล้ว

    Hi, Great video. There is one improvement in terms of space complexity. You really don't need to cache all that table. You just need the three values of dp[i+1][j] , dp[i][j+1] and dp[i+1][j+1] you can update these values as you go up and that's it. you dont need more memory. I thought it might be helpful to add it.

    • @igx_s2745
      @igx_s2745 ปีที่แล้ว

      You mean to declare 3 variables, lets say, diagonal = 0, right = 0, down = 0 ?

  • @luis-azanza
    @luis-azanza 3 ปีที่แล้ว +2

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

  • @srivigneshmurugesan1036
    @srivigneshmurugesan1036 3 หลายเดือนก่อน +1

    You don't write code, you write poems.

  • @ukuduck531
    @ukuduck531 2 ปีที่แล้ว +3

    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!!

  • @stringjourney
    @stringjourney 7 หลายเดือนก่อน

    Once the logic explanation was done...code looks easy peasy
    Great work.

  • @itsjustramblings
    @itsjustramblings 10 หลายเดือนก่อน

    Very well explained in a simple and direct way 👍. I initially saw this as inverse of levenshtein algorithm...without the initial values populated in each dimension since we are looking for the max common subsequence instead of no of changes required to turn one string to another. If you change the max comparison to min comparison and start from the beginning you can find the minimum changes required to turn one string to another. This algorithm will work if you iterate from beginning as well. It took me 3-4 hrs to understand levenshtein first time i came across.

  • @anandkulkarni2111
    @anandkulkarni2111 3 หลายเดือนก่อน

    good one!! one of the best explanations I have heard for why the solution of this problem works!! i.e diagonal (when matching chars ) vs max of side way movements during mismatch

  • @amankassahunwassie587
    @amankassahunwassie587 2 ปีที่แล้ว +1

    It can be solved in memory complexity of O(n). check my code.
    row = [0]*(len(text2)+1)
    for i in range(len(text1)-1, -1,-1):
    newrow = [0]*(len(text2)+1)
    for j in range(len(text2)-1, -1, -1):
    if text1[i]==text2[j]:
    newrow[j] = 1 + row[j+1]
    else:
    newrow[j] = max(row[j], newrow[j+1])
    row = newrow
    return row[0]

  • @tyro-mb3cv
    @tyro-mb3cv 11 หลายเดือนก่อน +23

    How is this a medium and not a hard 😢

    • @audioplatform6299
      @audioplatform6299 8 หลายเดือนก่อน +3

      I would categorize it as very very hard

    • @karthiksuryadevara2546
      @karthiksuryadevara2546 6 หลายเดือนก่อน +1

      The 2 d approach is hard to grasp, if you think in a recursive or map a decision tree in your mind it will be much easier

    • @athul.7744
      @athul.7744 5 หลายเดือนก่อน +6

      A useful way to think about that is, this kind of question needs to feel like a medium to you to know that you're at the level required to solve this question in an interview. So that's how much you have to improve. Just keep practicing and you'll find that noticing the patterns gets easier over time.

    • @chanrox69
      @chanrox69 หลายเดือนก่อน

      I was preparing for interviews and directly jumped to 2 DP. I kinda knew that there are 2 hard DPs but I thought they were 2 DP and 3 DP 😂

  • @abhilakshmaheshwari9360
    @abhilakshmaheshwari9360 2 ปีที่แล้ว

    You are a saviour man!!! If you have a solution for a question, I always visit yours first (not to mention I never need to visit any other video/blog after that)

  • @xhenryx14
    @xhenryx14 2 ปีที่แล้ว +1

    Thank you so much, I have had this problem and I never understood the solution until now! They never taught this algorithm in my DS and Algo class

  • @ruthviks
    @ruthviks ปีที่แล้ว +1

    Hey, buddy. I have been watching your videos for a while and learning a lot. I really have to say thank you for the time and efforts you put on. You are doing a great job.

  • @divyanshunautiyal4659
    @divyanshunautiyal4659 23 วันที่ผ่านมา

    incredibly intuitive explanation, thanks a lot

  • @HalfJoked
    @HalfJoked 2 ปีที่แล้ว

    Awesome video. We can actually make this O(min(m,n)) space because notice we only have to keep track of 2 rows at any given time. I found the most logical way to write this is to ensure text2 is the smaller variable and base our arrays around that. The reason for that is, we need the bigger string to be the outer loop and the smaller string to be our inner loop in order to make the tabulation work correctly, since we're swapping our rows after each inner loop, and our rows are based around the len(text2).
    The video solution is perfectly fine, but if you can start with that and get to an ever better space optimization in an interview, it'll look impressive!
    Passes all test cases.
    class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
    if len(text1) < len(text2):
    text1, text2 = text2, text1
    # text2 is the smaller one, so we base our rows around that
    cur_row = [0] * (len(text2) + 1)
    prev_row = [0] * (len(text2) + 1)

    for i in range(len(text1) - 1, -1, -1):
    for j in range(len(text2) - 1, -1, -1):
    if text1[i] == text2[j]:
    cur_row[j] = 1 + prev_row[j + 1]
    else:
    cur_row[j] = max(cur_row[j + 1], prev_row[j])
    prev_row, cur_row = cur_row, prev_row

    return prev_row[0]

  • @Dhruvbala
    @Dhruvbala 5 หลายเดือนก่อน

    I find this problem easier to understand in terms of a decision tree / recursive DP, then bottom up. And this can be optimized fairly easily to O(n) memory complexity.

  • @ventacode
    @ventacode 11 หลายเดือนก่อน

    Why not forward to bottom we can get the last value of the matrix right ? Is there any specific reason for bottom up approach ?

    • @SolutionHunterz
      @SolutionHunterz 9 หลายเดือนก่อน

      wondering the same since top down approach comes to my mind by default. Is there any specific reason that we are doing bottom up ?

    • @ventacode
      @ventacode 9 หลายเดือนก่อน

      @@SolutionHunterz didnt find any but some problems are solved only on that way

    • @FluffyBRudy
      @FluffyBRudy 9 หลายเดือนก่อน

      may be because we dont need to do array[array.length-1][array[0].length-1] to get the last index

    • @ventacode
      @ventacode 9 หลายเดือนก่อน

      @@FluffyBRudy um but as we are adding a row and a column initially it would be array[n][n] where n is the length of the string

    • @ventacode
      @ventacode 9 หลายเดือนก่อน +1

      @@FluffyBRudy understood your point, it would be different if the two strings compared with different length, thanks man !!!

  • @il5083
    @il5083 2 ปีที่แล้ว +4

    Using a top-bottom recursive approach will make the code easier to read in my opinion.
    The drawing walkthrough helped me to get a more concrete understanding, thanks a lot!

  • @tune6000
    @tune6000 ปีที่แล้ว +1

    Why does my code not work when I initialize my DP matrix like this: mat = [ [0] * (N2 + 1)] * (N1 + 1) , but it does work when I initialize like this: mat = [[ 0 for j in range(N2 + 1)] for i in range(N1 + 1)] ? N1 is len(text1) and N2 is len(text2)

  • @amitvyas7905
    @amitvyas7905 5 หลายเดือนก่อน

    The top down also works. That (top down) was the first thing that came to my mind when I first saw the question and when I saw this video, I got confused but when I saw the leetcode solutions then I found out I was right.

  • @tzifudzi
    @tzifudzi 2 ปีที่แล้ว

    Thanks!

  • @harshithdesai9989
    @harshithdesai9989 11 หลายเดือนก่อน

    As usual, its a wonderful explanation of the bottom up approach. Thank you so much!!!

  • @shankaranarayana6568
    @shankaranarayana6568 3 ปีที่แล้ว +2

    Its possible to optimise this further by calculating the values in the cells we need only right?

    • @WdnUlik2no
      @WdnUlik2no 2 ปีที่แล้ว +2

      That's exactly what I was thinking as well; it seems like it would be possible to only have two rows

    • @TheStefanV
      @TheStefanV 2 ปีที่แล้ว

      Yes

  • @binpan3602
    @binpan3602 3 ปีที่แล้ว +5

    I felt like top down is more intuitive to me in this case?

    • @johnpaul4301
      @johnpaul4301 4 หลายเดือนก่อน +1

      The top down is almost always more intuitive. Especially for 2D dp problems

  • @capooti
    @capooti 3 ปีที่แล้ว +2

    great video, thanks as usual. In this case I find it easier to iterate the rows and columns in regular (and not reversed) order.

  • @yogeshkhatri4555
    @yogeshkhatri4555 2 ปีที่แล้ว +1

    Man you are a good teacher ! Just found out about your channel and subscribed

  • @mehershrishtinigam5449
    @mehershrishtinigam5449 2 ปีที่แล้ว +2

    This was such a simple explanation! Thank you!

  • @prachibari731
    @prachibari731 2 ปีที่แล้ว +2

    You are AWESOME!! I wish I had known about your channel earlier.

  • @better_dead_than_red
    @better_dead_than_red 3 วันที่ผ่านมา

    Can someone help?
    What if it's "acb" and "abcde"? both 2 alternatives are valid, which one to choose?
    7:00

  • @mzn102
    @mzn102 2 หลายเดือนก่อน

    Sorry if by any chance this is a dupe comment. Exploiting the symmetry of the problem, it seems, one can pad on left and top and iterate from left to right going from the first row to the last.

  • @adityakulkarni2764
    @adityakulkarni2764 2 ปีที่แล้ว +2

    Your solution is great but how did u find out that this problem is actually 2D DP problem?

  • @thatguy14713
    @thatguy14713 2 ปีที่แล้ว +2

    Is it possible to implement a recursive w/ caching solution to this problem, similar to the other DP problems you have solved? If so, do you think you could describe the approach?

  • @Oleg86F
    @Oleg86F ปีที่แล้ว

    How it's possible to come up with such elegant solution directly at the interview without being genius and seeing the problem for the first time? )))))))

  • @AdityaSUnboxings
    @AdityaSUnboxings 10 หลายเดือนก่อน

    thank you so much bro u literally answered so much of my confusion.

  • @CharlesGreenberg000
    @CharlesGreenberg000 8 หลายเดือนก่อน

    How would you then use the DP table to obtain the actual best sequence? I suppose you start at the top left. If you find same symbol, move diagonally down. Otherwise take the max of bottom or right. Does that always work?

  • @arkady767
    @arkady767 7 หลายเดือนก่อน +1

    Its quite unclear to me, how am i even supposed to understand this is a 2D DP problem during the interview. It would be really helpful if you would go into the solution by following some kind of decision tree you would normally do for other DP problem and explain how that come to be a 2D DP table problem.

  • @meowmaple
    @meowmaple 2 ปีที่แล้ว +2

    Will the bottom up approach work if you start from the start of the substrings instead of at the end? Great video btw!

    • @bereketyisehak5584
      @bereketyisehak5584 ปีที่แล้ว

      yeap it does, but the length is save at the last element in the array.

  • @VSUKUMARBCE
    @VSUKUMARBCE 9 หลายเดือนก่อน

    great explanation Thank You NeetCode I am follow you through out my dsa journey

  • @tnmyk_
    @tnmyk_ 3 ปีที่แล้ว +1

    Your explanation made the solution so easy to understand! Thanks a lot for making this video, it was veryyy helpful! Keep up the good work!

  • @tomaparaschiv930
    @tomaparaschiv930 6 หลายเดือนก่อน

    what are the space and time complexities for this way of solving the problem? thank you

  • @referbaru9368
    @referbaru9368 ปีที่แล้ว

    i have two question
    1. is it posible if size of J is more than size of I ?
    2. what the LCS of this quest, if I = [a e d a b] and J = [d e b c a g] ? [e d a b] or [d e b a] ?

  • @city8390
    @city8390 3 ปีที่แล้ว +3

    Great explanation to understand! Thanks.

  • @zaidziad1456
    @zaidziad1456 3 ปีที่แล้ว +3

    Clear and simple, thanks a lot.

  • @adityaverma3247
    @adityaverma3247 3 หลายเดือนก่อน

    @NeetCode : Thanks for explanation BUT why and how we directly jump to Tabulation approach ? What's the brute force way to think and solve before jumping to Tabulation aka DP. That's what interviewer will ask, else it will look like I have memorized without showing brute-force approach. let me know your thoughts !!!!!
    Also what tool are you using for your visuals ? TIA !

  • @AsymptoteEducation
    @AsymptoteEducation 2 ปีที่แล้ว +1

    You have quality content, man. Cheers :)

  • @Cld136
    @Cld136 3 ปีที่แล้ว +3

    Another great tutorial. Much thanks!

  • @rishabhsharma6193
    @rishabhsharma6193 2 ปีที่แล้ว +1

    superb explanation as always... but can we just do it with 1D dp for last row then update it as we move forward, just like we did in unique paths?

  • @devonchia5976
    @devonchia5976 หลายเดือนก่อน

    can just maintain 2 rows (the last and 2nd last rows) to optimise for space complexity

  • @prabinlamsal74
    @prabinlamsal74 ปีที่แล้ว +1

    I am just starting leetcode and am at about 15 problems only. Please share how many problems you guys have done and some strategies that might be helpful.

  • @duanjianxiong2785
    @duanjianxiong2785 3 ปีที่แล้ว +4

    How did you come up with the idea of using the 2D grid?

    • @NeetCode
      @NeetCode  3 ปีที่แล้ว +7

      Mainly just from experience (i def didn't come up with it myself). This is a textbook 2D dynamic programming problem, once you understand it, many other problems become easier.

  • @vantran321
    @vantran321 2 ปีที่แล้ว +1

    Holy crap your stuff really helped me out man

  • @matthewsponagle5143
    @matthewsponagle5143 3 ปีที่แล้ว +2

    You are great at explaining these problems! thank you.

  • @kbillore28
    @kbillore28 5 หลายเดือนก่อน

    Superb explanation

  • @promethesured
    @promethesured 11 หลายเดือนก่อน

    I dont understand why most solutions have the intuition to start at the end of both strings and work back up to [0, 0]. It works either way, and to me it just made sense to start at the top left and end at the bottom right -- why does everyone intuit the other way?

  • @pranaygawas709
    @pranaygawas709 ปีที่แล้ว

    Hi is there is video where you solve this problem but we have to give the actual longest common subsequence?

  • @shaggypeach
    @shaggypeach 2 ปีที่แล้ว

    This was great really made me understood the concept. Thank you! Is there one for three strings?

  • @idobooks909
    @idobooks909 3 หลายเดือนก่อน

    Better than a Uni course in Algorithms.

  • @dohunkim2922
    @dohunkim2922 ปีที่แล้ว

    First thing that came to my mind when I saw this question was using two pointer. I tried so but failed. Is it possible to solve this question using two pointer? Also, do I have to memorize that questions like this requires the use of dp? Did you also memorize it or did it come to you intuitively? Thanks

  • @syafiq9095
    @syafiq9095 ปีที่แล้ว

    Can anyone explain to me why when the two alphabet does not match, we take the max of to the right and 1 cell below?

  • @anupamarao3783
    @anupamarao3783 4 หลายเดือนก่อน

    would it work if dp is of dimensions [2][j+1] ? because we only need i+1 th row to calculate dp[i][j]! (j is length of second string).

  • @sickboydroid
    @sickboydroid 11 หลายเดือนก่อน

    for me the top down approach (or recursive or memoized approach) is more intiuitive. I feel like code is take to me in that way

  • @mdmasudrana7406
    @mdmasudrana7406 2 ปีที่แล้ว +1

    You are the best as always. Keep it up, dear.

  • @marchaeldialde
    @marchaeldialde 5 หลายเดือนก่อน

    What application or software you used here? Thank you

  • @smtp_yurzx
    @smtp_yurzx 2 ปีที่แล้ว +1

    Everybody - NeetCode: Subsequence
    NeetCode: Subsekence

    • @NeetCode
      @NeetCode  2 ปีที่แล้ว +1

      lol thats true

  • @robinsharma7920
    @robinsharma7920 2 ปีที่แล้ว

    what about the block of code which creates the sequence

  • @VioletClaw816
    @VioletClaw816 2 ปีที่แล้ว

    Hi, how do I know when the problem is needed for a 2D grid dynamic programming? Thanks.

  • @DavidDLee
    @DavidDLee 6 หลายเดือนก่อน

    It's much easier to explain if you start with the full dfs solution. Otherwise, it's hard to give intuition for the the 2D array.

  • @yinglll7411
    @yinglll7411 3 ปีที่แล้ว +2

    Thank you so much! learned a lot from your channel

  • @moeenkamali1288
    @moeenkamali1288 8 หลายเดือนก่อน

    thanks for great tuts. i have a question. i can understand how algorithm work and follow up with it but after a while i figure out that i could not solve it before watching the the solution. i need to be able to solve it from ground up. with no primer knowledge. and that gives the answer that the first person has solved this problem used his long background on math and DP to solve it. so in general learning these algorithms means memorizing them as without knowing the base science its just a trick.