Edit Distance of two strings - Real world application

What is the edit distance of two strings? It is the minimum cost of operations to convert the first string to the second string. The operations allowed are addition, deletion and transition. We find the sequence of edits required to change the first to the second to in the cheapest way possible.
This algorithm using dynamic programming is used in many real world applications. The edit distance of two strings helps auto correct and word suggestion algorithms. These applications run when we type texts and messages on phones or computers.
The edit distance is also called the levenshtein distance between two strings. It has applications in auto correction, genetic material study and many other string processing applications. The most common use is that of auto correct in text editors, which use a variation of the edit distance algorithm to find closest matching words from a dictionary.
This is a dynamic programming solution which converts a recursive approach to a matrix. This matrix allows us to store values which are accessed repeatedly, and hence converts the simple recursion to dynamic programming. Each cell in the dp matrix depends on adjacent cells and the original strings for it's value.
I am looking forward to talking about approximate string matching in the next videos. Cheers!
References:
web.stanford.edu/class/cs124/...
www.geeksforgeeks.org/dynamic...
en.wikipedia.org/wiki/Levensh...
people.cs.pitt.edu/~kirk/cs15...
Code:
github.com/gkcs/Competitive-P...

[@sarkarsh5537]

Awesome video! So helpful!!! And the ---> "There'll never be a time when I'll add and then delete a character because that's stupid." was funny, had to pause the video to laugh for a moment. XD

[@gkcs]

😁

[@utkarshjain8024]

"Adding a character to A is equivalent to deleting a character from B", this was the one line that made me understand the entire problem. Really clear explanation!

[@huangleonard1557]

This is the very first edit distance tutorial which gives me no feeling of what the fxxx are you talking about. Excellent!!

[@aakashpathak21]

I was stuck for an hour because of the thing that how we can compute (i, j - 1) instead of ( i + 1, j)...saw a lot of videos but you are the one who actually explained :) Thanx bro!

[@vlogs.anurag]

exactly

[@saurabhjoshi9319]

I watch the whole video just because of this point Well explained

[@vinayak186f3]

I'm still stuck ,unable to backtrack , the goal was to convert pqqrst to qqttps , but he ended up with qqts 😥

[@BingumallaAmaresh]

The first part of the video explaining the function and the logic that follows for DP was what I just needed. Thanks :)

[@mohitksahu]

I watched many videos but could not understand the addition point. Till now, this is the best explanation I have come across for this problem. Thanks a lot, Gaurav. You are the savior.

[@sachinsharma905]

This is the most articulate explanation of this problem in the whole internet space.Thanks man.

[@pranavgaur6399]

The only reason I was able to understand the logic behind this problem(after watching several videos) was because you explained the logic behind insertion which no one else did.. keep up the amazing work

[@studgaming6160]

I didn't understand the how minimum function takes minimum of 3 elements of array from Tushar Roy's video, Then I came here and I UNDERSTOOD. Thank You brother. Keep making such awesome videos.

[@heenaagarwal6795]

When I search for a problem explanation on youtube, and I find your video at the top of the output list of my search, I get a sense of relief and a smile on my face. Now I will watch the video.

[@gkcs]

So glad to hear that Heena, thank you 😁

[@SurjitSingh14-c6i]

@@gkcs what is wrong public: int ct=0; string lcs(string s, string t) { int dp[s.length()+1][t.length()+1]; for(int i=0;i0) { // replace ct+=1; } else if(x==0&&y>0) { // insert ct+=y; } } int x=s.length()-p1; int y=t.length()-p2; if(p2>=t.length()&&p1

[@sanjarcode]

Learning and thinking like this is way better than just saying DP and then learning it.

[@lovehasija3995]

Awesome Explanation. I get shocked to see so many videos explaining the algorithm without the intuition or derivation. You did it really well, thanks for sharing. It's really helpful.

[@gkcs]

😁

[@anushkachakraborty8635]

Of all the edit distance explanation videos I have seen, This was the most passionately and relatable explained. Thankyou so much :)

[@musicislife1844]

Awesome video!! Thank you so much!! I have a humble request...please add more videos on dynamic programming problems the way you teach makes things look way easier than they are!! Keep it up!. Thanks a lot!!!

[@rohangarg5473]

No doubts in Edit distance now, thanks👍

[@rishabhb2688]

Very well explained ! Thank you !

[@nikhilgumidelli6308]

Brilliantly explained !

[@fullemptiness]

Coming from coursera course, suck in explaining the problem. Thanks, your explanation helped!

[@SATISHKUMAR-xk7cn]

Excellent explanation !! keep it up.

[@adlurirohith9528]

Adding a character in first string is logically deleting the last character in second string and the way that we do it is ( i+1 , j )-->( i , j-1) . I get it now. Great video btw.

[@Ankitbomb1]

That helped. Thanks man!

[@MegaArti2000]

Had to watch it twice, but I think I got it. Thx.

[@StarshipPapillon]

thank you gaurav, saved my life :)

[@gkcs]

Glad it helped!

[@jkrw3540]

Can you explain, why you have added and deleted from the end of the string and not from other part of the string ? Also, how do I know what character I am going to add in the first string to make it the second string ?

[@PriyankaSingh-pn8xv]

Awesome explanation

[@amitpurohit8816]

Sir your explanation is awesome....I watched tonnes of videos for this problem...But yours was the most effective..thank you!!

[@gkcs]

Thank you :)

[@amitpurohit8816]

@@gkcs I'm surely gonna recommend your dp videos to all my friends who are beginners in dp

[@vrdash]

Edit Distance that eluded me for so long makes so much sense now. I thought I would have to just blindly believe in the Algorithm :p

[@barshalamichhane6761]

Thank you so much!!

[@sahilkakkar5628]

Good Explanation, really helpful!

[@dznuts123]

Just to clarify, adding a character to string 1 is not literally the same as deleting a character from string 2. The minus 1 from string 2’s index is an abstraction, because after implicitly adding a character to string 1, the character at the index in string 2 is taken care of. We don’t need to minus 1 from string 1 index, because the index did not change during the additive process.

[@prateekkanujiya9775]

U r awesome bro. Respect

[@pranavkochhar9352]

VERY WELL EXPLAINED!!

[@innocent1029]

could you do a video on finding if a string is interleaved of two other strings?

[@aparichitsingh384]

Again a nice one. Thanks for this :) Cheers!

[@gkcs]

Thanks Aparichit! :) I am sorry I must have forgotten, but I don't remember thinking of a follow up video on Centroid Decomposition. Was it something I said? Centroid Decomposition: kzbin.info/www/bejne/Y33KlZRja8R0n7s

[@aparichitsingh384]

Sorry for this! I didn't get any notification for : kzbin.info/www/bejne/opnYY2x5apata9U Going to watch it tonight. Thanks a lot for reply bhaiya :)

[@gkcs]

Have fun! Btw, it has a mistake, so I added a correction video in the description :)

[@aparichitsingh384]

yes I'm talking about that correction video! (didn't get any notification for that. so, misunderstood)

[@rathinavelsankaralingam2929]

Thank you man! Just Thank You /\ You should live long :)

[@AkhileshKumarCSE]

Hello Gaurav, could you please help me understanding the at 12:58 - 13:05 here you are pointing at 'p' then saying add a char to get to 'q' ?

[@gkcs]

I have replied to your other comment on this :)

[@akashchatterjee5179]

Can anyone please say that why LCS -max length(S1,S2) logic fails...

[@anirudhatalmale5575]

outstanding

[@ShivamKendre-fc3su]

Really nice

[@AjayKumar-qm5fu]

Commendable effort bro

[@gkcs]

Thanks!

[@yobro7051]

this guy always seems so much energetic

[@saurabhsharma7123]

The concern of this video was why computing ( i + 1, j), instead of (i, j - 1) is wrong. That would lead to cyclic recursions!

[@gkcs]

Exactly!

[@priyeshshrivastava8425]

Hi Gaurav, if we are converting i+1,j to i,j-1 why are we still taking Ca the cost of addition, and not Cd?

[@sidharthsk3807]

U IIT Kharagpur

[@AayushThokchom]

​@@gkcs As Priyesh asked in the comment. My understanding is: this approach can only be applied if Cd < Ca. If Ca

[@gkcs]

@@priyeshshrivastava8425 Because although the operation is equivalent, we cannot change the costs of the operations. That's usually an input to the problem.

[@iiillliii1386]

proud of you my friemd

[@shreyanshtiwari3495]

great!

[@riturajjoshi5935]

Congrats on the new mic!

[@gkcs]

Thanks!

[@madhukiranattivilli2321]

I'm not sure if I clearly understood the concept of "adding to A is same as deleting from B". Lemme know if my writeup has flawa... (1) To implement dynamic programming technique, higher state should always reduce to a lower state. But in the case of adding a character to A, a higher state moves to an even higher state. So, this needs to change. 1 way is to delete character from B, instead (2) Difference in the sizes of strings A and B wud be 1 whether a character is added to A, or a character is deleted from B. So, to help the problem in (1), delete character from B (3) If A=pqqrst and B=qqttps, adding character to A would implicitly mean adding the final character of B to A as well. So A becomes pqqrsts. Now A and B have the same terminal characters. They have to be removed, because the algo does addition/deletion/transition always to the terminal characters, and so not deleting them will block the work of the rest of the algorithm. Hence, this change makes A,B = pqqrst, qqttp. And this would also be the state if s is deleted from B without making any changes to A (3) is the main point. (1) and (2) are supporting points Comments?

[@himanshusingh694]

Why you are considering going right towards p and going down towards q as deletion operation?

[@gkcs]

Check out the other edit distance video on the channel, which explains this.

[@LearnWithBahman]

Officially, I am a fan now, hopefully, one day we work together.

[@gkcs]

😁

[@archip3112]

Hi Gaurav, Please explain the case when the given two strings are of different size?

[@gkcs]

Hey Archi, The same algorithm applies! The matrix is of size M*N, where they M and N are the lengths of the two strings. 😋

[@archip3112]

you are right. Thanks !

[@yuvrajoberoi7834]

Excellent explanation of this problem. Also, you gave me a better appraoch to appraoch a proble. I have seen problems like design autocorrect feature etc. and there this thing can be very helpful right?

[@gkcs]

The autocorrect feature also has to take into consideration "probable words". For example, the word "runvwe" is closer to "timber" than we might expect. It's because our keyboards are designed that way. Our fingers also have typical ways of typing, and our mind make phonetic to spelling translations when we aren't sure of the spelling. All in all, it's a complex problem to solve. Neural networks have been seen to perform well in autocorrect applications. I would go with one of those :)

[@yuvrajoberoi7834]

@@gkcs Hey, thank you for giving your time to explain this.

[@kartikshet1]

Great explanation. I have one issue with dynamic programming, even if I come up with the recursive function, I find it hard to convince myself that it leads to the solution, I find myself stuck there.

[@gkcs]

It'll improve soon 😁

[@StarshipPapillon]

I think it will help you to trace your program step by step just like dynamic programming

[@AkhileshKumarCSE]

Hello Gaurav could you please help me understanding the concept of "Addition" here ? f(i + 1, j) = f(i, j - 1) ? Example given two strings "p", "q" , how will we convert "p" --> "q" using "Addition" operation ? As per logic which i understood from this video it would go like below :- f(1,1) f(1,0) = "q" --> " " (I guess this is 'j - 1' , effectively deleting from string "q" than adding in "p"). " " --> "p". (Addition : adding 'p' into NULL string). So basically we converted "q" --> "p" not "p" --> "q" which was the objective of Edit distance ? correct me if i understood wrong and help me understanding correctly please !

[@gkcs]

Both are equivalent. Converting A to B is exactly as expensive as converting B to A. So we pick any one and follow the steps. If the steps need to be printed, we can simply invert the operations that are optimal and the answer will be the same :)

[@AkhileshKumarCSE]

Thank you !

[@SportsMoments17]

13:13 we have not only one possibility, we have two possibilities because diagonally and vertically both are 4

[@visheshsrivastav2107]

Bhaiya can you upload a video for hardest gcd problem (codechef april cook off problem)

[@gkcs]

Coming up next :)

[@sulekhakumari-hs4gy]

want more from strings

[@alexanderrivera1938]

Can one of the strings be longer than the other?

[@gkcs]

Yes

[@Shrimangal100]

in d[1][1] your output is 0+1, but in d[1][2] it is only 1 and not 1+1. Kindly explain

[@hey.............]

great explanation Gaurav. Thank you for the help.

[@gkcs]

Thanks Varun!

[@hussainburhanuddin3705]

Wow, I really loved this video, Your explanation was really easy to understand. But, you didn't explain how the initial table would be created, at 10:59 , as I understood the table had 1,2,3,4,5,6 because Ca and Cd were = 1. I am not able to get my head around how the set up the initial table (end states) values for different values of Ca and Cd.

[@gkcs]

We make a table full of zero values, with dimensions equal to length of the two string m * n.

[@hussainburhanuddin3705]

@@gkcs Okay, that makes sense. But how would you fill the values for row 0 and column 0 if Ca,Cd != 1???

[@faizaomer5737]

Uffff Thanks Allah... Finally i got it output concept... Thank you Tutor

[@ayushgarg5929]

Jai Shri Ram🚩

[@ilikememes9052]

Ohhh God !! I can't understand anything in algorithms 😭😭😭. Have to watch multiple times.

[@mandeep2192]

because u like memes :P

[@anandchowdhury9262]

Tushar should see your videos..

[@varshavasan2130]

[@fullemptiness]

In the Edit Distance problem you need to know the source and target strings before solving the problem, but in the text correction application, you haave no idea what is the target string!

[@gkcs]

Yes. A frequency based trie is useful in those cases.

[@samarpanharit4268]

I am unable to understand 😶😶

[@gkcs]

Which bit?

[@samarpanharit4268]

Got it now after watching it thrice😂 thanks for asking

[@stalera]

using the approach described above for words "smitten" and "arbrikitten", the actual difference should be 5 but I get as 4. the issue I see is that i is repeated in the second string and that is causing the issue. I'm sure I'm missing something if you could help me understand. Thanks.

[@gkcs]

I tried the code: github.com/gkcs/Competitive-Programming/blob/master/src/main/java/main/java/videos/EditDistance.java The difference is 5. Where did you get 4?

[@stalera]

@@gkcs my bad, shouldn't the difference be 6? arbrik 6 characters and remaining are same. If I use the LevenshteinDistance algorithm it gives 6. Am I missing something here? The issue is because arbrikitten has 2 'i' which is being considered both the times for 'i' in smitten. Shouldn't it be considered only once?

[@stalera]

hey man, do you think I'm missing something here? it could be some silly mistake if you can help me figure out.

[@gkcs]

ideone.com/jjou1K

[@stalera]

@@gkcs appreciate your efforts to respond to each of the comments man. that takes hell lot of patience. Hope you've not kept an assistant to do that ;)

[@artihlec]

young Addy Osmani

[@axc4280]

Far from Topic Can you tell me what is difference between C++ and Java when we learn it and from what kind of matter we have to be attentive...

[@pallavisompalli2689]

Will you marry me? 😭

[@thebibhuty]

This channel is related to programming not bharat matrimony ;)

[@karun4663]

@@thebibhuty savage

[@rajatpal1019]

lol :)