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

📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions

Question: Write a program that takes two strings and computes the minimum number of edits needed to transform the first string into the second string.

Examples:

Input: "Saturday" and "Sundays"
Output: 4

Why:
In: "Saturday"
1.) Delete the first 'a' ("Sturday")
2.) Delete the first 't' ("Surday")
3.) Replace 'r' with 'n' ("Sunday")
4.) Insert an 's' at the end ("Sundays")
Out: "Sundays"

Our 3 Operations To Fix Character Mismatch:
- Insert
- Delete
- Replacement

++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is number 17.2 in "Elements of Programming Interviews" by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

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

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

[prakad]

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

[edgarsanmartinjr.]

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

[bhushanshinde]

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.

[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

[wen-tseshao]

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

[chetansahu]

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.

[duncduncan]

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

[cwash]

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.

[diegocastro]

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.

[willw]

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.

[hussammostafa]

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

[deepakdas]

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

[bugontheice]

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

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

[anujapuranik]

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

[monikshamurthy]

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 👍

[arunkumar-vwlk]

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.

[b]

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