Edit Distance Between 2 Strings - The Levenshtein Distance ("Edit Distance" on LeetCode)

[@BackToBackSWE]

Table of Contents: (and correcting small mistakes) My Humble Leetcode Beginnings 0:00 - 0:34 The Problem Introduction 0:34 - 1:50 The Notation We Will Use For Substrings 1:50 - 3:17 Situation 1: Equivalent Characters (Subproblem Drop-Through) 3:17 - 4:47 Situation 2: Mismatch, Do A Replacement Operation 4:47 - 6:10 Situation 3: Mismatch, Do An Insert Operation 6:10 - 7:01 Situation 4: Mismatch, Do A Delete Operation 7:01 - 7:50 Dynamic Programming Table Walkthrough (Bottom Up) 7:50 - 14:46 Time Complexity 14:46 - 15:12 Space Complexity 15:12 - 15:34 Please Validate Me 15:34 - 15:56 Mistakes In Speech: 4:57: I said "y does not match m", I meant "y does not match h". My bad. 10:28: I say "Replace has an edit distance of 0. What I mean is that if we did the replace operation we would add 1 to the edit distance between the strings " " and " " ." I was not fully clear, but what we do is add 1 to the minimum of the edit distances that result from a certain operation on the cell we are sitting on. The code for this solution is in the description. In my walkthrough, I put A's characters on the columns and B's characters on the rows. The code puts A's characters on the rows of the DP table and B's characters on the columns. Either way, that is an implementation detail, as long as you understand the operations and how they relate our substrings you should be solid to answer this question in the interview.

[@katiesissons8205]

you're the best, thank you

[@BackToBackSWE]

@@katiesissons8205 sure

[@nayemalaboni8318]

@@BackToBackSWE Thank you so much for such perfect explanation, mashallah your explanations are always so perfect and you're so passionate about it, since you are having trouble getting back to people or answering their questions maybe you can make a video addressing the questions in comments? also can you please post a new link to the solution code its not working for me

[@maxxmahh]

Very nice explanation, thank you! However, what should you do if when you have repeating characters? This algorithm doesn't work if you compare "a" to "aa", it will give you edit distance 0, while it should be 1!

[@maxxmahh]

Ok, the explanation here is not correct, as many similar once. Here is the correct solution: kzbin.info/www/bejne/jqnbYZVtmc92qNU

[@Arcketer]

I'm an experienced engineer and I'm absolutely blown away by how well you are able to explain these topics. Absolutely amazing video, thank you so much.

[@BackToBackSWE]

hahaha, aw, thanks

[@edgarsanmartinjr.4278]

Perfectly explained. Love how you pointed out that it’s one thing to memorize the patterns but it’s another thing to understand what each cell means and what we are actually doing in every cell

[@prakad97]

Dynamic programming is sick to understand..but when you do it is the best feeling..!! Thanks for a great explanation..!!♥️

[@BackToBackSWE]

sure

[@bhushanshinde8358]

I am experienced professional currently working for HP n I am totally amazed by the understanding of the topics and especially the amount of dedication u put in to convey the same to others. That's a unique talent to have..all the best for the future! Keep making videos. Happy coding.

[@BackToBackSWE]

Thanks

[@thelilnatey]

Yo I had a kind of rocky grasp on minimum edit distance until I watched this video. This is exactly how I needed it explained to me

[@BackToBackSWE]

nice

[@wen-tseshao321]

Every SWE going to have an interview must to know this channel, this is the most clear DP explanation video I've ever seen!!

[@BackToBackSWE]

ye - for the gram

[@chetansahu1505]

You explain so bit by bit that you leave no stone unturned. Nobody can ask you doubt it is that precisely explained. Keep up the work bro. Hats off.

[@BackToBackSWE]

yo

[@tsehousung3552]

This is by far the best explaination I've ever seen about this topic, so clear and elegant. Thanks a lot.

[@BackToBackSWE]

sure.

[@b9944236]

The smaller table is so useful to understand, what an amazing teacher !

[@diegocastro7434]

Hey man, just wanted to say I really, really appreciate you making these videos, they are clean, concise and better than literally any others out there. I've gone through most of your videos and I can honestly say that I have learned more from you than from any professor I have ever had.

[@deepakdas4513]

I have never seen a better explanation to this "The Levenshtein Distance" problem. Just awesome.

[@BackToBackSWE]

thanks

[@duncduncan3719]

i really like that you go through literally every step of the process, even if it means saying the exact same sentence five times in a row haha

[@siliconvalley-z4j]

Really good explanation, and accent is very friendly for the foreign, expression is very clear

[@hussammostafa]

Man! You're brilliant! I'm doing my masters now and this is the best explanation i've seen so far! Thanks

[@BackToBackSWE]

thanks

[@willw4096]

7:54 "DP tables are not about remembering numbers. It's not about remembering patterns of how you fill it out. It's about knowing what is going on, why we do it this way, and what the sub-problems are." Very nicely said. I feel that.

[@BackToBackSWE]

Thanks! subscribe to our 5 day free mini course for some cool content backtobackswe.com/

[@kumarprateek1279]

One of the best explanation so far for any dynamic programming problem!!

[@BackToBackSWE]

thanks

[@chetansahu1505]

You are the godfather of all mentors bro. :)

[@BackToBackSWE]

yo

[@wanderer.1993]

dude...best teacher ever! FANTASTIC

[@BackToBackSWE]

thx

[@bugontheice]

I just wish that this awesome video had subtitles/captions, for the hard of hearing people like us :(

[@surajlalgupta6536]

Man, you are the best. Amazed to see how easily you explain such complex topics.

[@BackToBackSWE]

thanks

[@anujapuranik2000]

Great explanation. It is definitely a difficult problem and you made it so easy to understand. Thanks!

[@BackToBackSWE]

sure

[@shivanathmahalingam3466]

This is so beautiful now thanks to your wonderful explanation. I don't comment often on KZbin but this video truly deserves it.

[@BackToBackSWE]

hey

[@dderudito]

You are a really good teacher. I've got it this time!!!

[@BackToBackSWE]

nice

[@srikanthtumpudi536]

The Way your explaination , the way you built the requirements to solve problem extremely helpful. I habituated to browse for your videos when a problem is ambiguous and if I need any basic knowledge about that problem . My teacher suggested to watch your videos and follow your way of thinking a problem and solving. Thanks for decreasing speed while explaining :)

[@BackToBackSWE]

haha, nice, thx

[@ujjwaldeswal1924]

I can't believe. one of the finest explanation I got. Nice job bro. Impressive buddy ^^

[@BackToBackSWE]

sure

[@mushymush223]

I'm so glad this video exists. Currently taking the algorithmic toolbox course on coursera, and the lectures on the topic are horrendous. Some of the worst lectures I have ever seen in my entire academic life. And then there is this guy who actually seems to enjoy teaching and puts effort into it.

[@SzechSauce]

Thank you so much for this brilliant explanation!

[@BackToBackSWE]

sure

[@looklook6075]

i can not express how much you have helped me to understand dynamic programming.

[@0x1h0b]

"it's not about the pattern , it's about the sub problems" ... i think i just lost my innocence ...best

[@BackToBackSWE]

lol

[@darshansimha2166]

Beautiful explanation. Stopped watching at 8:20 and solved it myself. Thank you for this.

[@arunkumar-vw1lk]

I was really puzzled how this pattern matching works. Even though i know the code i couldn't understand what it does. But this video gave a clear explanation.Excellent job, keep rocking.

[@BackToBackSWE]

Ye

[@kingelvisalive]

The grid helped me to visualize, the repetitive explanation helps to confirm understanding. I understand this now. Thank you very much.

[@badal1985]

Your videos are really really good. Thanks for the good work!

[@BackToBackSWE]

Thanks for taking the time to watch them. -Ben

[@wangrobbie6867]

No one explained more clearly than you on EditDitance. Thx!

[@BackToBackSWE]

sure!

[@Ashish.Shukla9]

You are "GOD" best teacher on youtube so far...

[@BackToBackSWE]

haha

[@mercuriallabs9]

Well said! its not about pattern its about sub problems. One of the best explanation on youtube...

[@BackToBackSWE]

thx

[@bodang2425]

Thanks a lot! Crystal clear and impressive!

[@BackToBackSWE]

thanks

[@efenadiralumni6547]

man simply you are the best. please do not stop

[@BackToBackSWE]

ok

[@venkydaggubati9375]

Thanks for the great explanation. I have a question though, in the "Our key" table below, should insert and delete swap places, since we are transforming A to B? 9:00 - 9:48 in the video, or am I confused?

[@4sky]

In the video it is correct, but why the key is set up that way is not explained very well. It took me a long time to grasp it after many hours of looking at it. Let's say we have to transform "benyam" to "e". (Please look at the chart in the video for reference.) "" b e n y a m "" r i e d * "e"? We have to INESRT "e" into the empty string. If we go diagonal to the replace cell, we transform the "benya" part of "benyam" into "" and we just get "m". Then how do we turn "m" into "e"? We have to REPLACE "m" with "e". If we go left to the delete cell, we transform the "benya" part of "benyam" into "e" and we just get "em". Then how do we turn "em" to "e"? We have to DELETE "m" to get "e"

[@BackToBackSWE]

thanks for this, old video, remaking one day

[@southern-sunshine]

This is the first video which properly taught me the logic. I clearly understood difference between insert and replace which was always so confusing to me. I have seen many videos just going through formula without rational behind it. Thanks a ton again

[@BackToBackSWE]

nice!

[@darshitgandhi9122]

Sir actually in the key part while solving the table , the places of replace is ok, but the insert and delete places shouldn't be interchanged??

[@BackToBackSWE]

I'm not sure, I did this a while back

[@darshitgandhi9122]

@@BackToBackSWE okay sir...np... And thank you so much for uploading all these videos...it has helped me a lot😀🙌🏻

[@BackToBackSWE]

@@darshitgandhi9122 ye

[@12nites]

Yess, thanks for posting this, I thought I was going crazy. The easiest way to see it is during the pre-filling of the table (base cases) at 8:55

[@BackToBackSWE]

@@12nites my b, if I messed up, I don't remember

[@bassantgamal8873]

you are amazing, I spent two days trying to understand this problem before finding this video, I understood it in 15 minutes only, that is awesome. I do really like how deeply you are able to explain that.

[@BackToBackSWE]

nice

[@captainlennyjapan27]

Thank you for the video but I need help! 4:42 Why does it become A[0,3] -> B[0,2] , and not A[0,3] -> B[0,3] ?? I don't understand why we are comparing 4 char string to 3 char string all of a sudden

[@BackToBackSWE]

So what we are doing is a subproblem decomposition and seeing how each action causes a new subproblem to be birthed. For A[0,3] -> B[0,2] aka "beny" to "eph", if we do a replacement to repair the last character mismatch, then the new subproblem is both strings without that character (because we are going to replace the last character to "repair" the first string). The new subproblem (or problem left to solve) is "ben" to "ep", this is our new task to transform and compute the edit distance of. 1 plus "ben" -> "ep" is the answer to the edit distance if we choose to replace from the state "beny" -> "eph". That 1 represents theoretically doing the action. The code explains each well: github.com/bephrem1/backtobackswe/blob/master/Dynamic%20Programming%2C%20Recursion%2C%20%26%20Backtracking/editDistance.java

[@captainlennyjapan27]

Ah that makes sense..! Thanks you so much!

[@ahmedpatel1995]

@@BackToBackSWE Small suggestion, would recommend to cover such underlying presumptions in the video on spot

[@BackToBackSWE]

@@ahmedpatel1995 ok

[@vman049]

​@@BackToBackSWE At 4:56, why do you say, "Y does not match M"? Did you mean "Y does not match H"?

[@blatanthamma6624]

I have to say there are tons of explanation for this good old question but none of them are as good as yours, it's super clear and it actually makes sense even for someone like me who's kinda new to DP

[@Ayoub-adventures]

1:37 "there are brute force ways to do it, we are going to look at the dynamic programming approach" I don't like this statement a lot, I would rather deduce the DP from the brute force.

[@BackToBackSWE]

yeah

[@cwash08]

I've recently understood this from watching a bunch of videos and watched this to strengthen my understanding. There are no doubt great videos since I was able to understand from them, but I have to say thank you Benyam for explaining the details of not only the algorithm, but how it relates to what we know about things like sub-problems and where the decisions in the table are coming from. Basically you don't just say what the algorithm is, you explain it. I didn't really see that from other videos, I just looked for patterns and listened very, very carefully if there was such a small explanation given (maybe like 2 seconds in the video). Basically the way I understand these problems now are that when we have problems like optimization from many combinations/permutations (min/max), it is usually exponentially brute force and we avoid talking about the recursive solution in the first place, because the sub problems allow us to use just a few of the previous values we know about by solving bottom up from the base case. Instead of using recursion and using the memoization top down approach, we can create a test case with a table (essentially an array, can be 2D) using a bottom up tabulation approach and utilize a pattern we find there for our algorithm, keeping in mind the meaning of the values we are filling in and what the rows and columns represent. In this example, (3, 2) represents the sub-problem where we solve for the substrings "ben" and "ep". For two empty ("") strings we can just return 0. We can use the table we create (provided that what what we are filling into the table is correct) and see how the sub-problems are related and how it helps us solve the current problem. To show additional information from our tabulated approach solution, we use the last value in our table (array) and work backward to find the operations when values change. For edit distance, I mean we can find what the actual edits are by working backward with our pattern where values change starting from the last value in our array. All of this typing and I have only done a couple very basic ones, so what I say can be BS or missing something. But I rather understand before doing a bunch of problems, its hard for people to explain DP I guess, which is why many give the advice to just solve a bunch of problems.

[@BackToBackSWE]

nice!

[@gurtagel]

The only thing that I don't get is why going left, up, or diag-up represents delete, insert and replace operations respectively. The intuition of using the minimums makes sense but this is what I can't wrap my head around.

[@peterparser995]

Check the base cases (first row/column) in one case we are incrementing the amounts of deletes to arrive at "". Other case is incrementing the insertions from "" to our expected result. For the replace you compare the smaller substrings diagonally (i-1, j-1) and add 1 only if the last chars being compared are different.

[@BackToBackSWE]

I did not make this clear but the key is that each cell is a subproblem. When we go left, up, or diag-up it changes the substrings that we take the Levenshtein distance against. The Levenshtein Distance of where we are at is the min of the Levenshtein Distance yielded from the min of the 3 operations PLUS ONE. PLUS ONE because we are choosing one of those operations and hence executing it. @Mathieu Neron is right, the base cases make things more clear and we won't know anything until we drill down to them in the top down approach which is what the code sample I provided in the description does. Just keep pondering on it and it will click. I apologize for my unclarity. Continue asking questions as the arise and challenge what you know.

[@gurtagel]

@@BackToBackSWE Thanks this helped! I get it now

[@BackToBackSWE]

@@gurtagel ok cool

[@FloShaban]

@@peterparser995 But the delete and insert don't make sense to me. Since we got from b to empty string by deleting, but that's considered insertion on the key? (looking at 0,0 0,1 and 1,0 )

[@monikshamurthy2466]

Really like the way you take time to explain the sub problems instead of simply pointing out the pattern. Awesome explanation! 👏Keep up the good work 👍

[@BackToBackSWE]

ok

[@xxxxxjjjjj62]

your explanation can't be clearer. still I forget everything after my eyes are off the screen.

[@BackToBackSWE]

it takes practice, you have to code it.

[@isaiahvictor6773]

the way you teach reminds of how i teach the kids (ages 7-14) at my work how to code. Just the way you talk and go over the same things multiple times. Its so much easier to understand.

[@MohamedSamy-kr6ug]

I'm impressed, how could you do this ! Go on you are awesome :D

[@BackToBackSWE]

thx, I read a textbook haha, and the explanation is decent

[@SzechSauce]

Back To Back SWE which textbook if I may ask?

[@BackToBackSWE]

@@SzechSauce Kleinberg & Tardos: Algorithm Design - dry but fire

[@SzechSauce]

Back To Back SWE Thanks will have a look!

[@BackToBackSWE]

@@SzechSauce ye

[@samarthsoni6103]

best ever explaination and channel to learn coding

[@BackToBackSWE]

thanks

[@gabrielraphaelgarciamontoy1269]

This was amazing! Thank you! Subscribed and liked :) You should do one with the stone problem or maze part II

[@BackToBackSWE]

I think that's on my list...I have like 250 questions scheduled rn so I'm pretty sure I'll hit the fundamentals you'll need. We will see.

[@vinayakbiju]

I was initially confused midway, but going through the whole video cleared all my doubts. Thanks a lot

[@JamshadAhmad]

1:50 Instead of making pairs of (startIndex, endIndex) I think it would have been better to make pairs like (startIndex, length) so that we don't run into negative indexes.

[@BackToBackSWE]

That sounds reasonable - I don't remember the implementation enough to be 100% sure this works but sounds fine

[@devershichandra2241]

I agree. That's how C++ substring operation work too.

[@mimosapoon6038]

You explain it very well. And I really appreciate you walked through the calculations for every single cell in the table. You save my day. Thanks

[@BackToBackSWE]

Hahaha, ok, sure

[@VarunVermaUSC]

I applaud the effort you've taken to explain the fundamentals, great solution. My 2 cents. Please try not too move too much and obstruct the view. It's a little distracting when someone is trying to focus on the board.

[@BackToBackSWE]

Ok, let me go back in time a few months and redo this one, brb

[@kueen3032]

haha I was about to comment the same thing but then I thought someone might have already commented this and here you are anyway Ben, love your videos!!

[@BackToBackSWE]

@@kueen3032 hey

[@kueen3032]

@@BackToBackSWE hi ! What are you upto these days? Any new internship or are you giving all of your time in teaching programming?

[@BackToBackSWE]

@@kueen3032 We'll see

[@itzboyon6983]

Respect, dude. You deserve a ton of respect for how you taught us this topic.

[@BackToBackSWE]

thank you

[@AbinayaThiyagarajan777]

Thanks for explaning clearly. One suggestion I would like to tell is there is no pause or a break, please slow down, you to need to take a breath, and give viewers time to process the information too.

[@BackToBackSWE]

Yeah I know, I'm working on it

[@santosh1809]

hahaa lol, there is pause btn man, there is a fking pause btn for some reason

[@BackToBackSWE]

@@santosh1809 hey

[@santosh1809]

@@BackToBackSWE hey thanks man for contributing into open source competitive programming lessons

[@BackToBackSWE]

@@santosh1809 sure

[@SR-we1vl]

Far than obvious, this man is a legend indeed!

[@BackToBackSWE]

I am normal

[@Madeinchinaagain]

my 2 cents: don't focus so much on how you repeat each point or operation. With the extra time you're spending on repeating each operation verbally, you could be giving the WHY or the logic behind the "transformation" or sub-transformation.

[@BackToBackSWE]

ok.

[@nynom]

Man!! Thank you soo much. I came across this problem so many times, couldnt even understand it in my ungrad algorithms course and you just made this problem so simple and easy to understand. Thanks a bunch!!!

[@BackToBackSWE]

sure haha, I thought this explanation was "ok". I did this video a while back and don't even remember how well I explained it. I have a remote feeling that it was a mid-decent explanation.

[@nihargadkari5914]

Awesome explanation. I looked at a lot of other videos but the way you break the problem down and outline the operations helps a lot. Please keep up the good work.

[@BackToBackSWE]

Sure, thanks

[@macroxela]

This is the best explanation of dynamic programming I've seen, even better than the MIT OCW. Not many people spend time on the tables which I believe are quite useful when learning.

[@BackToBackSWE]

nice.

[@MohsenKhamis-xk8yl]

bro

[@natesouverlai4916]

Hands down the best explanation of the problem.

[@angelicatorresgarcia5228]

thank you SO much !!!!! when you said its not about the pattern something in me clicked and i just hope my brain can work like yours someday. i really appreciate the way you explain things !! thank u forever !!!!!

[@Pedr0Diniz]

Thank you very much for this explanation. I failed an interview that had this question and even though you said it's not about the pattern, the pattern did help me at least scrible the problem and get a feeling of it instead of being completely clueless.

[@chiranjeevipippalla]

I never ever thought I would love DP tables. The thing you said - It’s not about the patterns, it’s all about the sub problems. You stick that in my mind so hard that I started looking for sub problems. Thanks brother 🙏🏻

[@SevenRiderAirForce]

You are a good teacher and should feel good about that.

[@dylanhan9577]

Hey, really appreciate the help. It's always nice that you took the initiative to take a step forward and help others understand this concept.

[@BackToBackSWE]

yea

[@animeshjain4045]

Never seen such a well explained solution....Thanks

[@polybius9089]

This has to be, hands down, the best and easiest to understand explanation for this subject! Thank your for this video and your work, you've earned a new subscriber! :D

[@lucheeno]

Best explanation so far. I'm amazed by your communication technique.

[@myhoop]

Great explanation. Very intuitive. Tried to understand this on Wikipedia first, without success. This video made it clear to me.

[@BackToBackSWE]

Great. And eh....Wikipedia is pretty hard for even me to understand. They go into very DEEP depth and stay mathematical. Much more exact and informative than me, but I think the key is that one understands something before getting the full details. Thanks for watching.

[@sainimkar815]

Damn! This is the best explanation for edit distance problem on the entire internet. Amazing! Please make more videos

[@mohamedessam3054]

your explanation is more simple and clear than that i hear from stanford course

[@BackToBackSWE]

haha nice, it is alright

[@hakanklc4327]

OMG! You're amazing sir. This was the best explanation I've ever seen.

[@chengjiang7051]

What an excelent explannation. I could not believe i figured it out. Thanks a lot !!!

[@BackToBackSWE]

It's an ok explanation haha, thx

[@leonewu7171]

This is the simplest turtorial I have ever seen abount edit distance in youtube

[@sgerodes]

This explanation is magic. Thank you for explaining the meaning of operations of the algo.

[@woodylucas]

No one mentions how you just showcased your growth. Like you stated you couldn't solve a simple problem--I don't mean to offend anyone, by saying simple, to where you are now. I love it man! It gives individuals like me confidence, because there was a time there was problems on there that were labeled easy and I couldn't solve them, and it was a real confidence drainer. Now look you're solving these dynamic programming problems w/ great conceptual overviews.

[@BackToBackSWE]

ye

[@MooMooKhanThe1st]

First I ignored this video because there is a guy with a whiteboard and guys with whiteboards usually explain stuff not very clearly. But this is totally a different case, I understood everything. Thank you!

[@micado6]

I saw this algorithm in class and honestly couldn't follow it at all... I was hoping someone could explain it better on here, and you did!! thank you so much for this!

[@Randomisticful]

You are a born teacher. Wow!

[@samgak_imbap862]

I am always so slow in understanding algorithm, but I immediately understand after watching !!! The video is soooooo helpful!

[@baldbadger7644]

that's was a lesson in a logical and clear manner. thanks a lot

[@BackToBackSWE]

thanks and sure

[@Pickyricky69420]

Wow. There is so much to unpack! I am watching this one few hundred times. Good job Benyam!!!

[@yueranzhang2350]

most clearly edit distance explanation ever seen!

[@BackToBackSWE]

thx

[@androidnexus5336]

Even I'm Japanese, your English is easy to understand. Your explanation is super awesome. thanks :)

[@BackToBackSWE]

Nice, haha, I never considered that that'd be an issue when I started this channel hmm

[@ankithas1868]

You are superb bro i simply took paid course of algoexpert this is crystal clear explanation with intuition building i should have bought your course

[@BackToBackSWE]

We are building something exceptional in the coming year

[@mihirpandey7831]

I was having a hard time understanding this problem.. but this lecture completely clear this concept. Thank you

[@IntegralDeLinha]

Thanks a lot! You made it really clearer! I couldn't see each cell as a subproblem before your video.

[@mucahitalper8184]

I opened 6 different tabs of videos explaining this topic, thankfully watched your video first. I'm so clear about this know thank you tons ^^

[@BackToBackSWE]

great

[@srinivasadineshparupalli5139]

Awesomeness. Explanation blown my mind. Superbly understood the topic.

[@WIN_1306]

u got a new subscriber ,just keep posting such informative videos bruh

[@cabutchei]

You, sir, are amazing, no need to say more!

[@BackToBackSWE]

thx

[@joshkariyathu8902]

Thanks a TON for these amazing videos. Your explanation not only helps you understand the solution rather also helps you figure out how to think and arrive at it. Love your work!!

[@sarthakdhingra2168]

Really liked how you covered all the different situations!

[@BackToBackSWE]

thx