Edit Distance between 2 Strings | The Levenshtein Distance Algorithm + Code
HTML-код
- Опубликовано: 4 июл 2024
- Link to the Code: gist.github.com/JyotinderSing...
Link to the problem: leetcode.com/problems/edit-di...
Link to my GitHub: github.com/JyotinderSingh
Link to my Website: jyotindersingh.com/
Timestamps:
00:00 - Problem Introduction
02:36 - Algorithm Walkthrough - I
09:52 - Algorithm Walkthrough - II
25:15 - Coding Walkthrough
_______________________________________
Some great channels to learn more:
Tushar Roy: / tusharroy2525
Errichto: / @errichto
Nick White: / @nickwhite
Kevin Naughton Jr: / @kevinnaughtonjr 
Наука
Great video. I watched 2-3 other videos on this same problem, but I still struggled to understand the algorithm. Your explanation was clear and easier for me to understand. Well done.
Thankyou so much for the explanation!! I have my finals next week and this helped a lot.
Excellent explanation! I was trying so hard to understand how this algorithm works and now it's clear, thank you very much
Explicit explanation. I got confused using a different video; but this helped me understand. Thank you!!!!!!!!!!!!
Thank you so much for this video. It really helped me to understand how the Levenshtein distance works!
Excellent presentation. It's the first one I've seen where one can quickly understand the process. One still needs to make the mental effort to convince oneself that the method does indeed work in all situations. If the demonstration of the method, however, is enough for some to assure them that it works, then working out a proof that it does can be deferred.
I literally couldn't understand the UCSD course and your video helped me out big time. Recommending this to anyone who struggles tbh
even if i understood it, you made a fanstastic job. thanks my man
Thank you. At first, I feel difficult to understand the problem. Thanks to your video, it is clear and easy to implement.
Thank you for this video, it has tremendously helped me understand this problem for my algorithms class.
thanks for the great explanation! after watching a few videos on this question, i finally get it.
Really good explanation! Thank you so much!
Excellent Explanation...your video is best to understand levenshtein distance algo
You, sir, are a LEGEND!
One of the best explanations, thanks :)
Best explanation!! Thank you
Best explanation I've seen on it though, thanks!
Just wanted to point out though that there is an off-by-one error in the code. The for loops need to be up to
Hi Jyothi, I was able to follow the example and explanation and had same matrix as per your explanation. Want to understand how you concluded that minimum number ops will be4? How can I find out required operations from the DP table?
It's simple. Create a 0th cell in the top right and but 1-.... for each word to create rows/columns. Once you have done that its super easy: Look at the top, top left, and left column from where the first open cell. Whatever the lowest number you see is you add 1 to it and that's your answer. In the case that the letters correspond ("e" and "e") use whatever value is in the top left column and then continue to the next combo. Awesome video though
Very nicely explained, Sir..
Thanks for making this video it is so helpful
Good luck dude
Nicely explained...!
Gud work..!
Gawdddd the struggle i took to understand this in class😭😭 ....... thanks a lott sir
Exellent explanation!!!
Its very great explanation, im very understand it now
hi sir in the insert operation why the target string is remaining the same ? why we are only reducing the source string by one character?
cool video with brilliant explanation.
nice explanation Jyotinder. I would like to more about the coding. Do you have some material I can look to understand, how you execute the same.
Thanks for video. you're the best
Thanks a lot!!!
Best explanation. Thank you!
Glad you liked it! Please consider subscribing for more such videos!
Thanks for making this video. I liked that you added replace, delete, insert,current position in a small grid on the bottom left. It helps visualization.
Btw what software do you use for your digital pen?
I'm glad you liked the video! I use procreate on iPad for the visuals
@@JyotinderSingh thanks!
Thanks great explanation
Thank you
thank you
Thank you! You are much better than my teacher
It's an honour to hear that! Thank you!
for the worked example starting at 10:17, in my opinion the explanations only work if we try to convert word2 to word1.
Very nice video bro!
Thank you! Be sure to subscribe for more videos!
17:13 i could not understand how we can perform replace and insert ?
min of the (Neighbouring elements +1 ) so it is either replae vs insert. But
To convert "re" to "d" the way i see is replace 'r' by d and delete it.
Or am i missing something?
nice!
How did you get the grid? I don't understand
Thanks bro! 💪🏻
Glad to be of help bro! ♥♥♥
Thank you!!
Glad it helped you out! Please consider subscribing for future content!
why how the previous cells represent delete replace add?
Effective solution.
Glad it helped! Remember to hit the like button and subscribe for more content!
thanks you!!!
Glad you liked the video! Be sure to subscribe for more!
This is only correct iff the costs for all operations are the same and their cost is one. Those are two big assumptions. It's not because there's a mismatch that you can just add a one automatically.
exactly...
02:49 why not check the 1st index ?
why the last .
Hi there! Great explanation. I don’t understand how we know that the diagonal cell is a “replacement” I get the logic for insertion and deletion, but not the replacement.
Hey, the logic is that when you replace a letter - you basically match the last letter of the the two words by replacing one of them. This reduces the sub problem to the rest of the word that is to the left of the last two letters (which now match after the replacement). Now, we use the DP table to find the solution to this sub problem (of transforming the remaining words). The solution to this problem lies in the upper left diagonal cell of the current cell in the table. Why is that? Because if you remove the last letter from both the words - that's where you end up. Try re-watching the white board explanation in the video where I explain this.
@@JyotinderSingh Wow, thanks for the fast reply! Really appreciate it!
but sir, this is not levenshtein algorithm. coz for substitution it adds 2
you have the first row wrong. to match empty string on text takes 0 cost
At 22:23 I didn't understand why the [2,7] cell became 6 instead of 5. Why did it pick the 6 from the top-left instead of 5 from the left? Surely, the lowest number was the 5 to LEFT of [2,7], not the 6 from the ABOVE-LEFT.
I thought we would always choose the lowest number to make sure that we followed the cheapest path (least number of operation) to get to the state that cell represented.
Hi, if you look closely - that case is of a MATCH. It means we don't need to perform any operations (to convert e to e) and we can directly look at the remaining sub problem (which is converting 'replac' to 'd'). That sub problem is represented by cell [1,6].
Hope this helps.
I dont understand a shit, why e to e is not zero? Why any letter to any letter is not one? Nothing makes any sense
Thanks for the great explanation
Thank you! Be sure to subscribe for more content!