Minimum Edit Distance Dynamic Programming

Given two strings and operations edit, delete and add, how many minimum operations would it take to convert one string to another string.
github.com/mission-peace/inte...
github.com/mission-peace/inte...

[@mylilcritic]

Legend! I couldn't figure it out after an hour of looking at my lectures but within 3 minutes of you explaining it just clicked! Thank you!

[@shubhampathak1080]

I have got my exam tomorrow and this video really helped me to understand the edit distance algorithm thoroughly. Probably one of the best explanation that one can find on KZbin for edit distance. Thank you very much !

[@vaibhavmourya65]

mine is tmrw.. 8 years same vibe

[@pvpk1994]

Man! Respect! Awesome Job! ..i spent hours together breaking my head on this before seeing this video! Lucid Explanation!

[@ksankitha]

Tushar your explanations are extremely clear and have been immensely helpful Great job .Looking forward to more videos from you .Please keep them coming !

[@tuncdogukan]

I got the idea of the algorithm quickly. It's a nice and clear implementation with good explanation. Thanks for the effort to pass on the knowledge.

[@aashkas]

Thank you, I had been looking at some dp question for days. Your explanation and graph really became a breakthrough.

[@FF-ne2qz]

You didn't say why this works. It is very important!

[@bioinfo9386]

He actually did, even in detail- you´d better watch the clip again..

[@azklinok]

He did not. He told us the method, not its proof.

[@wanghaochen3515]

What kind of proof do you need? If they are the same, then do nothing, if not, add 1 more operation to whatever gets the least in previous ops. To me, the logic is pretty obvious.

[@azklinok]

The logic is obvious to all of us. I want to know WHY the logic works, and gets us the right answer.

[@wanghaochen3515]

azklinok Well. First of all, if two characters are same, you don't do anything, that's clear right? If not, then there's 3 possible moves: delete, replace and insert. Suppose your rows represents str1, cols represents str2. If you wanna delete, you go back to previous column, which is T[i][j-1], because you'd like to retrieve the last character in str2. Similarly, if you wanna insert, you go back to previous row, which is T[i-1][j]. For replacing current character, you need to retrieve last character in both str1 and str2, which is T[i-1][j-1]. At last, you get the minimum among the above 3 moves and plus 1 to it to get T[i][j]. I'm not sure if I articulate it in a proper way, at least that's how I understand this problem.

[@digusbickus]

I've been slamming my head against this problem for days. Cheers! You made it very understandable and easy to grasp.

[@somebodymk]

This helped me out so much! Thank you!

[@mr.mystiks9968]

Awesome video. I already knew how to write out the DP table and but deriving the edit operations being done from the table was the crucial part I did not understand. This was a big help.

[@studywithrobin2715]

You explain it a lot better than some of the newer videos.

[@ertagon]

Simple and straightforward. I looked at 3 different videos before this. This is a really good explanation.

[@MegaMiley]

Thank you!! This is the second time already a video of you made a problem 'click' for me :D, it all makes so much sense now!

[@sharpdemon]

Wow very nice man! I will definitely go through all your videos to brush up my algorithms!

[@wreno7879]

Thank you for uploading this video. It's extremely helpful!

[@sbahuddin]

I spent hours and couldn't figure it out. You explained the concept so nicely in just 9 minutes.

[@namazbaiishmakhametov6424]

Crap, man, in a little over three months it will be 6 years since you shot this video, and it helped me today! Thanks a lot, Tushar, and I hope you're doing well these corona-days!

[@DignsagYT]

Until this video I could not wrap my head around it. So thank you very much. Straight to the point.

[@DominicClaxton]

I didn't understand this until I watched your video. Thanks a lot!

[@cppprogramming]

Tushar, your explanation of how to populate the table, and then how to work it backwards to identify operations was awesome. Thank you.

[@4ythere]

Hey, I feel you should also hover over optimal subproblems and what a state of the DP represents, For example, In this question, when not equal, you take the min of(top,left,diagonal) , where in you should explain that the top refers to inserting a[i], left refers to deleting a[i] and diagonal refers to editing a[i]. On a side note, you should have mentioned the case where the cost of edit, insert and delete are different.

[@sankethb.k642]

Thank you

[@manoharyedla360]

@@sankethb.k642 worst lecture

[@abhishekk.3977]

7:00 - Diagonal ( EDIT) 7:25 - Left ( DELETE ) Top -> Insert (Implied)

[@beanlighter9491]

yes but this is how indians study can you guys recommend me a more detailed lectures?

[@Cube2deth]

@@parmoksha +1 I don't know why they complain! His videos are not meant for proof or theory or how he thought of the solution just how to solve a problem, which is what we are all trying to learn

[@mariusz4742]

Thanks a lot, that's so easy when you explained it :)

[@pikapika8282]

Awesome video! Thanks for posting, this has helped me a lot!

[@rialaurent-hughes7191]

Thank you, that was perfect. Explained better than my lecturer

[@latheefjunior]

Bro, you've done a wonderful job here. Thanks!!!

[@ghakol]

thank you so much for this video!! i have a test on this in a few hours and this explanation was really helpful :)

[@younusahmed23]

hey thank you for this video it was extremely helpful and it helped me understand a complex concept in only 10 minutes. Awesome video

[@a50x]

Great explanation, easy to understand, really helped me to clearly understand DP

[@xlOogh0stoOlx]

Thank you so much. I have computer algorithm exam tomorrow and this video really helps me. You're the man.

[@elyxthelynx]

This is really useful! Thank you for the video!

[@achilles165]

Great series of videos to prepare of interviews... already subscribed to your channel... One suggestion though... instead of directly jumping to the matrix right from start... it would be awesome if you could explain the solution for a min or 30 seconds, in terms of what you will be doing before jumping to solving of the table. Although you kind of mention the formula in the end, but it would be better if it is verbally explained at the beginning and then mathematically written at the end. That would help people in understanding that how DP can solve this problem in the first place.

[@bernardoalvarenga2607]

Excellent explanation, great clarity. I've seen a video from CS50 on the subject that was a mess. This is great.

[@maielshazly6054]

Your explanation is really clear. Thank you very much

[@xxbighotshotxx]

Thank you Tushar, seriously, I think I'm going to pass my algorithm final tomorrow because of these videos

[@amith89rm]

I salute this guy!!! Thanks so much for the video. I was cracking my head to solve this problem. your explanation helped me understand in less than 10 minutes

[@sagnikrana7016]

Hey Amith, I understood the approach. Could you help me explain why this method works?

[@AssSlurry2998]

Pause the video at 3:35 and see this intuition , 1) when first string is 'a' and second string is 'a' , the cell has 0 as its value , that is the minimum number of inserts/delete/edits =0 . so dp [ 1 ] [ 1 ] =0 2) when first string is 'az' and the second string is 'a' , for converting second string to first , 1 insert is required , so dp[ 2 ] [ 1 ] =1 3) When first string is ' a ' and second string is 'ab' , for converting second string to 1 , 1 delete is required ,i.e delete 'b' . so dp[ 1 ] [ 2 ]=1. Now comes the cell dp[ 2 ] [ 2 ] . If str1[ i-1 ] != str2[ j-1 ] There are 3 possible ways to do it . 1) Possibility 1 : Use dp [ 1 ] [ 2 ] , that is if i delete b from second string , both strings become equal , so if z is added to the first string , we can use dp [1 ] [ 2 ] that contains the number of deletions to make string first =string second . So we can just insert one element Z to string first to make them equal . 2) Possibility 2 : Use dp[2][1] ,that is if insert z in the second string , both strings become equal , so if i added b to the second string , we can use dp[2][1] that contains the number of insertions to make string first=string second . So we can just delete one element B from the second string to make first string =second string. 3) Possibility 3: use dp[1][1] , that is , if string 1 ='a' and string 2 ='a' , minimum number of edits required to convert string 2 to string 1 =0 . SO if z is added to the first string and b is added to the second string , we can just edit b in string 2 and make it z to make strings equal. Finally we assign dp[i][j] as the minimum of the 3 :) , hope it helps

[@tanishq2766]

Hey thank you so much! This was really what I was looking for!

[@eliasmorag]

Good job! It really helped me

[@KameshwaranTheInsane]

I owe you so much Perfectly presented. You had explained this within 10 minutes Thank you very much...

[@rahilgupta1244]

Thanks a lot Tushar! Very well explained

[@priyanksaxena18]

Beautifully explained. Thank you.

[@perfectfalse1]

THIS WAS A HUGE HELP. Thank you for posting this.

[@chintalapativenkataramarahul]

Thank you dude! Nice explaianation

[@oborotsuki6sai]

Thanks a lot for the explanation!! So much easier to understand

[@ahmedboutaraa8771]

shout out to you man. really empowering content.

[@cadmonyuen6141]

You are doing a really good job. Keep up man.

[@novicaovuka5480]

Man, you helped me a lot. I have an exam soon. And I have to learn a lot of code which I don't understand. After watching your video, man, that code is so easy. Thanks a lot.

[@amanbhandari349]

You learn code!!??? Wtf

[@josegermanparra6064]

Thanks for a clear and concise explanation!

[@evergreen7781]

I can say that, you have the best Dynamic Programming KZbin tutorial in the market ❤️❤️❤️

[@Toxx98]

Thank you for your videos, helped me understand it properly.

[@malvikark124]

Great explanation. Thanks so much!

[@ankursuri3853]

This is the best explanation I have found sofar. Thanks so much Tushar! Keep up the good work.

[@uditkanotra9393]

please understand where the formula came from Use f[i][j] to represent the shortest edit distance between word1[0,i) and word2[0, j). Then compare the last character of word1[0,i) and word2[0,j), which are c and d respectively (c == word1[i-1], d == word2[j-1]): if c == d, then : f[i][j] = f[i-1][j-1] Otherwise we can use three operations to convert word1 to word2: (a) if we replaced c with d: f[i][j] = f[i-1][j-1] + 1; (b) if we added d after c: f[i][j] = f[i][j-1] + 1; (c) if we deleted c: f[i][j] = f[i-1][j] + 1; Note that f[i][j] only depends on f[i-1][j-1], f[i-1][j] and f[i][j-1], therefore we can reduce the space to O(n) by using only the (i-1)th array and previous updated element(f[i][j-1]).

[@yuhua1994]

Helpful video! Totally understand after watching your videos :)

[@sarikaranjitkumar174]

Thank you for the great explanation!

[@ts-gaming-29531]

Very good short video . Good job.

[@ryan_forte2097]

This was very informative and helpful. Thankyou!

[@alvaro1121]

Thank you my friend! Very clear explanation of the algorithm

[@rulisastra]

Wow, great explanation... Thank you!

[@afiyatiamaluddin9034]

Thank you very much, this is my AHA MOMENT. This is what I'm looking for all this time.

[@jarias14]

Thank YOU for explaining this in detail.

[@dimitrisdimitriou6969]

Tushar! Awesome! Great job!

[@prashantjindal8697]

Your videos on dynamic programming are extremely helpful....!!! Great Job Tushar.....!!!!

[@chilipeppero]

Excellent friend, I could understand this algorithm, thanks a lot!

[@monapanah]

Bravo! one of the best teachers in this field! thank you

[@AnonymousDeveloper1]

You are awesome man, great explanation.

[@masoomakram4270]

Awesome explanation... Finally I understood. Thank You.

[@hopem6501]

Thank you so much. You really helped me understand :)

[@logicraju]

Awesome video, bro ! Was very useful !

[@danielbogolin8880]

Thank you so much. Keep up the good work! :)

[@agrimasrivastava2060]

Thanks a lot Tushar. One of the best explanations I came across. :)

[@TheManawaha]

Thank you, really helped me a lot :)

[@nikkiv7919]

Thanks Tushar this is great

[@umerwaqas5943]

wonderfull way to teach. it was so difficult for before watching this. thanks

[@ayanpaul27]

Short and crisp explanation.. Thank u so much... Finally i got to understand this

[@Harow77]

Thanks sir, cleared all my doubts in a short time.

[@ghensao4027]

thank you dude. your explanation is very clear

[@deepakkumarshukla]

Thanks bro! Much appreciate your effort.

[@AntiochsAdvocate]

Got stuck on this problem in an NLP textbook and this really helped tysm :)

[@gururajraykar9254]

Just awesome video. Was searching short video which i can learn this algorithm.

[@yusniamaliah4522]

i have been looking for tree edit distance theory, and this is the best explanation ever. i just watch at once, i really understand. thanks for sharing education. I'm subscribing U right now..

[@eshwareducationsolutions2091]

this is the best explanations. Thanks much. Your implementation is very simple too. I really helped for my exam.

[@dhanashreepawar9329]

Good and clear explanation. Easy to understand!!!

[@marinakantar8648]

Thanks a lot! It was very helpful :)

[@tristangrobler4950]

This is really cool! 9 years since posting and it helped. Nice work!

[@GlobalContentThatWeNeed]

Good explanation of Minimum Edit Distance Algorithm!

[@Daniel-to5jd]

the best video i have found on this topic so far, you explain it better than in a paid coursera course

[@vyshnavramesh9305]

In MIT DP 3 video, Eric explains the logic behind the "min(the three cells)" beautifully. In short its the representation of insert, delete, replace.

[@ashdavv]

Thanks for the videos .. Great explanation

[@nischalguruprasad600]

Great video! Thank you very much

[@quynhlq8832]

very easy to understand. Thanks a lot!

[@jonesbrothers134]

Excellent video sir, Thanks a lot.

[@AbdurRahman-mv4vz]

Thank you for the helpful video.

[@muthurajramalingakumar2361]

Thanks for the upload! The intuition behind taking the Min of three cells would be helpful.

[@antonioprocentese3253]

The best explanation ever! Thank you !!! :))))

[@abhijithtk]

I think this is one of the best explanations out there for this problem. Thanks much. Your implementation is very simple too. love it.

[@YanuarTriAdityaNugraha]

+Abhi Tk Absolutely, very easy to understand. Keep going.

[@milesstephenson4873]

Thanks, Tushar. Very clear explanation.

[@dearn5900]

Thank you for this video, you help me a lots

[@zoyajaveed2186]

Thank you so much. Saved my time 😊

[@PAIETES19]

Best explanation on the internet! Thanks for the video

[@vamsik6457]

Thank you Tushar! So helpful.

[@jeffhansen1554]

Thank you so much for this vid!