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

i dont get the operation it was very confusing

Thanks for the awesome explanation!

tnxxx

Your explanation is very confusing. Ive seen much better examples

I'm sorry i'm probably dumb as f but i cannot figure out for the life of me why if the last characters match then the optimal transformation from A[0;i] to B[0;j] has the same number of steps as the transformation from A[0;i-1] to B[0;j-1]. Like formally why must that be true ? I understand even less when the last characters aren't the same

Les hoooooooooomes ❤️

Amazing

TY so much great explanation and I dont even speak english that well! Love from italy

ive left more confused than before. :(

Incredible video.

Amazing explanation on dynamic programming! For this example it would be a really cool to add transposition which adds a nice extra special case.

I am currently readin EPI book and have decided to cover almost all of it, and this question just threw me off the chair.
But you sir saved my ass, THANK YOU !
BTW I started reading this book thx to you, you mentioned it in one of ur videos.
Recursion and DP sections are significantly harder than what ive encountered so far in this book.

Did you go over these questions multiple times or just moved on to leetcode after ? In thinking of re-tracing my steps because these questions are so important, more than leetcode imo.

Ben I want to learn to code after watching this video 👊🏽

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

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

Hi there! I noticed a small mistake in your explanation. In JavaScript, substring(0, 0) returns an empty string "", not "b". The correct behavior is that substring(start, end) includes the character at the start index but excludes the character at the end index. For example, substring(0, 1) returns "b", substring(0, 2) returns "be", and so on. Just wanted to clarify in case anyone is following along. Thanks for the great content!

Thank you for this. I wanted to know if there is an equivalent edit distance for Javascript code?

Wow this was great! Thanks a lot :)

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!

Amazing!

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.

thanks alot

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

I actually think there is a way easier approach if that is the only 3 rules we can have.
It just neccessary mean...
Edit distance = string size - Max(match in order)

Max(match in order) would mean...
Etc abcdefg is my aim, with aceg, the Max(match in order) would be 4.
In more complicated case like abcdefggfedcba against acfegfedcbd...
I think it is solvable with technique like min max in sub array
Which should make it easy to solve and potentially solvable in O(n^2)?

really helpfull

i don't comment often but i have to say nice work, your explanation was very helpful

Very well explained, thank you! :D

Thank you, this was very good, thank you. I appreciate it.

What gets me really depressed is when you open this on leetcode and it is written "medium"

Currently struggling with this problem. Tried DP but still struggling with the base case and the definition of the overall problem function to be honest. My only consolation is that I have ONLY spent a day on it and tried a few approaches, but nothing sticks. Thanks for putting this solution!

you are awesomeeeee!!!!!!

its so nice thanks

You are an excellent teacher!Thank you

Hey!! @BackToBackSWE, I am finding it difficult to understand exactly why (i-1,j-1) will be replace, (i-1,j) will be insert and (i,j-1) will be delete? Also confused on exactly why we added a column and row for empty string. This might be a wrong question, but trying to understand this so that I will get an intuition when I am solving similar question.

Can you compare it with money change and explain why you cannot solve it the same way?

This is the best video for edit distance

Great explanation. I think that the square you show as "Our Key" is a actually incorrect...naturally incorrect from labelling viewpoint only as the logic of the algorithm is not flawed. Shouldn't the box say [replace, delete] in the first row and [insert, You are here] in the third row? I think it should

Excellent explanation, no need to memorize patterns. Thank you

Leetcode only rates this medium difficulty, which is a bit of a joke to me. Its one of the only popular problems I wasnt able to solve on the fly and had to purposely look up an algorithm for.

Thank you!!

IF HAD A TUTOR LIKE YOU I WOULD BE AT PLACES, BETTER PLACES

such a perfect explanation, the only one who made me understand it thank you so much!

Greate explanation

fantastic explanation

Thank you!

Dude, you are amazing!!!!!

i have a confusion about how 0th row and 0th column is fixed using the below code. I understood the video explanation btw:

public static int EditDistance (String s1, String s2){
int m = s1.length();
int n = s2.length();

int[][] dp = new int[m+1][n+1];
for (int i = 0; i <=m; i++) {
dp[i][0] = i; //ISSUE: row wise filling---1st column fill-----insert----n length of s2
}
for (int j = 0; j <=n; j++) {
dp[0][j] = j; //ISSUE row filling----delete----m lenth of s1
}
for (int i = 1; i <=m ; i++) {
for (int j = 1; j <=n ; j++) {
if(s1.charAt(i-1) == s2.charAt(j-1)){
dp[i][j] = dp[i-1][j-1];
}
else{
dp[i][j] = Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1])) + 1;
}
}
}
return dp[m][n];
}
}

Thank u very much but next time take it slow