Edit Distance between 2 Strings | The Levenshtein Distance Algorithm + Code

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

[@chadsmith71]

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.

[@porrakroth]

Excellent explanation! I was trying so hard to understand how this algorithm works and now it's clear, thank you very much

[@Stelios.Posantzis]

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.

[@uKhyta]

Thank you so much for this video. It really helped me to understand how the Levenshtein distance works!

[@pianomoonpunch]

Thankyou so much for the explanation!! I have my finals next week and this helped a lot.

[@Ali-zg4fy]

I literally couldn't understand the UCSD course and your video helped me out big time. Recommending this to anyone who struggles tbh

[@amarieelohor7319]

Explicit explanation. I got confused using a different video; but this helped me understand. Thank you!!!!!!!!!!!!

[@thecurlykale]

thanks for the great explanation! after watching a few videos on this question, i finally get it.

[@TP-rs2un]

Thank you for this video, it has tremendously helped me understand this problem for my algorithms class.

[@muslimahmukbang417]

Really good explanation! Thank you so much!

[@swatiujgare8921]

Excellent Explanation...your video is best to understand levenshtein distance algo

[@og1kenobi973]

You, sir, are a LEGEND!

[@angeltran381]

Thank you. At first, I feel difficult to understand the problem. Thanks to your video, it is clear and easy to implement.

[@hosseinsafari7514]

One of the best explanations, thanks :)

[@zekicaneksi]

even if i understood it, you made a fanstastic job. thanks my man

[@rezaderakhshan1732]

Thanks for making this video it is so helpful Good luck dude

[@hind8426]

Best explanation!! Thank you

[@akshanshbhandari7619]

Nicely explained...! Gud work..!

[@jjque322]

Exellent explanation!!!

[@umadas1831]

Very nicely explained, Sir..

[@jasonzavaglia]

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

[@obarlanytska3051]

cool video with brilliant explanation.

[@user-fm1ut3ug1s]

Thanks for video. you're the best

[@mohammadramadhoni3285]

Its very great explanation, im very understand it now

[@youthought878]

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

[@aarushisharma7856]

Thanks a lot!!!

[@annvilprince5083]

Gawdddd the struggle i took to understand this in class😭😭 ....... thanks a lott sir

[@egdcuyagecuysadgcuys]

Best explanation. Thank you!

[@JyotinderSingh]

Glad you liked it! Please consider subscribing for more such videos!

[@trysha2340]

Thank you

[@engabeer]

Thanks great explanation

[@Popdad]

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?

[@ritwik121]

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?

[@airsheebs]

nice!

[@janogashoamatalaah7764]

thank you

[@gabrielyassunaga3447]

Very nice video bro!

[@JyotinderSingh]

Thank you! Be sure to subscribe for more videos!

[@nmnjn]

Thanks bro! 💪🏻

[@JyotinderSingh]

Glad to be of help bro! ♥♥♥

[@janlugtmeijer4347]

Thank you!!

[@JyotinderSingh]

Glad it helped you out! Please consider subscribing for future content!

[@user-fo7qp9vi4f]

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?

[@ioulios12]

Thank you! You are much better than my teacher

[@JyotinderSingh]

It's an honour to hear that! Thank you!

[@AshishSharma-wj4jz]

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.

[@musings2134]

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?

[@JyotinderSingh]

I'm glad you liked the video! I use procreate on iPad for the visuals

[@musings2134]

@@JyotinderSingh thanks!

[@anuragchowdhury4034]

How did you get the grid? I don't understand

[@armellekadia4997]

thanks you!!!

[@JyotinderSingh]

Glad you liked the video! Be sure to subscribe for more!

[@user-kt2qd2qc2y]

Effective solution.

[@JyotinderSingh]

Glad it helped! Remember to hit the like button and subscribe for more content!

[@rapmusa]

why how the previous cells represent delete replace add?

[@KNO476]

for the worked example starting at 10:17, in my opinion the explanations only work if we try to convert word2 to word1.

[@BlokeBritish]

02:49 why not check the 1st index ? why the last .

[@deepikasingh3122]

but sir, this is not levenshtein algorithm. coz for substitution it adds 2

[@oxymoron6701]

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.

[@7oeseven793]

exactly...

[@Kidpunk98]

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.

[@JyotinderSingh]

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.

[@Kidpunk98]

@@JyotinderSingh Wow, thanks for the fast reply! Really appreciate it!

[@kutilkol]

you have the first row wrong. to match empty string on text takes 0 cost

[@TormodSteinsholt]

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.

[@JyotinderSingh]

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.

[@ragnarlothbrok367]

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

[@anaresthiana]

Thanks for the great explanation

[@JyotinderSingh]

Thank you! Be sure to subscribe for more content!