The edit distance algorithm is very popular among the data scientists. It's one of the basic algorithms used for evaluation of machine translation and speech recognition.
The naive approach would be to check for all possible edit sequences and choose the shortest one in-between. That would result in an exponential complexity and it's an overkill since we actually don't need to have all possible edit sequences but just the shortest one.
Here is an example for this approach in LeetCode.
Use D[i][j] refer to the edit distance for word 1 and word 2. D[i][j] = edit distance between word 1[1...i] word 2[1...j].
It turns out that one could compute D[i][j], knowing D[i - 1][j], D[i][j - 1] and D[i - 1][j - 1].
If the last character is the same, i.e. word1[i] = word2[j] then
D[i][j] = 1 + min(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1] - 1)
and if not, i.e. word1[i] != word2[j] we have to take into account the replacement of the last character during the conversion.
D[i][j] = 1 + min(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1])
The above assumption means:
1.When the last character is the same:
- [i-1][j] -> [i][j]: edit distance of change i-1 of word 1 to j of word 2, plus one more distance of deleteing the i of word 1.
- [i][j-1] -> [i][j]: edit distance of change i of word 1 to j-1 of word 2, plus one more distace of adding the j of word 2.
- [i-1][j-1] - 1 -> [i][j]: edit distance of change i-1 of word 1 to j-1 of word 2, no need more distance of minus one first and plus one then
2.When the last character is not the same:
- [i-1][j] -> [i][j]: edit distance of change i-1 of word 1 to j of word 2, plus one more distance of deleteing the i of word 1.
- [i][j-1] -> [i][j]: edit distance of change i of word 1 to j-1 of word 2, plus one more distace of adding the j of word 2.
- [i-1][j-1] -> [i][j]: edit distance of change i-1 of word 1 to j-1 of word 2, plus one more distance of replacing the i of word 1 with j of the word 2
The code is below:
class Solution {
public int minDistance(String word1, String word2) {
// got length of word 1 and word 2
int len1 = word1.length();
int len2 = word2.length();
// if one of word is empty, need to change all of another
if( len1 * len2 == 0 )
return len1 + len2;
// build the dp array
int [][]edit = new int[len1+1][len2+1];
// build the basic case for change word 1 to empty
for( int i = 0; i <= len1; i++ )
edit[i][0] = i;
// build the basic case for change empty to word 2
for( int j = 0; j <= len2; j++ )
edit[0][j] = j;
// calculate
for( int i = 1; i <= len1; i++ ){ // from 1 bc it means the actually length
for( int j = 1; j <= len2; j++ ){
if( word1.charAt(i-1) == word2.charAt(j-1) ){
edit[i][j] = edit[i-1][j-1]; // no need to change
}
else{
edit[i][j] = 1 + Math.min( edit[i-1][j-1], Math.min( edit[i-1][j], edit[i][j-1] ));
}
}
}
return edit[len1][len2];
}
}
Hello to every one, since I am genuinely kkeen oof reading
this website’s post to be updated regularly.It cwrries nice data.
Hello, I enjoy reading all of your article. I like to write a little comment to support you.
I enjoy what you gujys aare usually up too.
This type of clever work and reporting! Keep uup the very ggood works guys I’ve added you
guys to my own video.
Taxi moto line
128 Rue la Boétie
75008 Paris
+33 6 51 612 712
Taxi moto paris
Outstanding story there. What happened after? Good luck!
I do not even know how I ejded up here, but I thought this post was great.
I don’t know who youu are butt certainly you are going too a famous
blogger if you are not already 🙂 Cheers!
Everyone loves what you guys are usually up too.
This sort of clever work and reporting! Keep up the fantastic works guys
I’ve added you guys to our blogroll.
Hi mates, its enormous paragraph regarding tutoringand completely
defined, keep it up all the time.
We stumbled over here from a different page and thought I should check things out.
I like what I see so now i am following you. Look forward to
going over your web page repeatedly.
I really love your website.. Pleasant colors & theme. Did you build this website yourself? Please reply back as I’m trying to create my own personal blog and would love to know where you got this from or just what the theme is called. Many thanks!
These bags are manufactured with a product that stops the heat from getting inside. An identical condition applies in cold weather. Because the bag is so small, you can make it around anywhere you want.
You must take part in a contest for one of the best blogs on the web. I’ll recommend this web site!
Hey! I just wanted to ask if you ever have any problems with hackers? My last blog (wordpress) was hacked and I ended up losing months of hard work due to no backup. Do you have any solutions to protect against hackers?
A person necessarily help to make severely articles I might state. That is the first time I frequented your web page and thus far? I surprised with the research you made to make this particular publish extraordinary. Great activity!
Nice blog here! Also your site loads up fast!
What host are you using? Can I get your affiliate link to your host?
I wish my website loaded up as quickly as yours lol
whoah this blog is fantastic i love reading your posts. Keep up the good work! You know, many people are hunting around for this info, you can aid them greatly.
It’s actually a cool and useful piece of info. I am happy that you just shared this useful information with us. Please stay us informed like this. Thanks for sharing.
Wonderful post however I was wanting to know if you could write a litte more on this topic? I’d be very thankful if you could elaborate a little bit more. Many thanks!
Very good blog! Do you have any tips for aspiring writers? I’m planning to start my own blog soon but I’m a little lost on everything. Would you suggest starting with a free platform like WordPress or go for a paid option? There are so many choices out there that I’m completely confused .. Any suggestions? Thanks!
Wow, fantastic weblog format! How lengthy have you been running a blog for? you made blogging look easy. The whole glance of your site is fantastic, let alone the content material!
Keep functioning ,remarkable job!
Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your point. You clearly know what youre talking about, why throw away your intelligence on just posting videos to your blog when you could be giving us something enlightening to read?
http://peoun.com/__media__/js/netsoltrademark.php?d=premiumporntrailers.com/girlfriendsfilms/
http://canyonscapes.com/__media__/js/netsoltrademark.php?d=premiumporntrailers.com/girlfriendsfilms/
Hey just wanted to give you a quick heads up. The text in your content seem to be running off the screen in Opera. I’m not sure if this is a format issue or something to do with browser compatibility but I figured I’d post to let you know. The design look great though! Hope you get the issue resolved soon. Kudos
http://twcservices.net/__media__/js/netsoltrademark.php?d=bestpornsites.club/
It’s going to be end of mine day, except before end I am reading this great
post to increase my experience.
http://apricityllc.com/__media__/js/netsoltrademark.php?d=premiumporntrailers.com/girlfriendsfilms/
You have covered this subject skillfully.
You have covered this subject skillfully.
Youre so cool! I dont suppose Ive read anything like this before. So nice to find somebody with some original thoughts on this subject. realy i appreciate you for beginning this up. this amazing site is something that is required on-line, somebody with a bit of originality. valuable problem for bringing something new to the net!
I was suggested this web site by my cousin. I’m not sure whether this post is written by him as no one else know such detailed about my problem. You are incredible! Thanks!
Howdy! Do you know if they make any plugins to protect against hackers? I’m kinda paranoid about losing everything I’ve worked hard on. Any tips?
Excellent write-up. I absolutely appreciate this site. Keep it up!
I’m impressed, I must say. Seldom do I come across a blog that’s both educative and entertaining, and without a doubt, you have hit the nail on the head. The problem is something not enough folks are speaking intelligently about. Now i’m very happy I came across this during my search for something concerning this.
i love baby gifts and i love to give baby gifts to my baby and also the my sister’s baby`
Nice post. I learn something more challenging on diverse blogs everyday. It will always be stimulating to study content off their writers and rehearse a little something from their store. I’d want to apply certain using the content on my own weblog regardless of whether you do not mind. Natually I’ll provide you with a link on the web weblog. Thanks for sharing.
I appreciate the way you have concluded this article …
Hello gentleman do you’ve got new links ? I enjoy article evolve for my friend ‘ ..
A large range of information on Technology is to be discovered by surfing on the web, as well as making use of the internet search engine. Taking your first actions – this is what the understanding we have offered is fixated. What you need to do now is take your first steps, understand that you won’t accomplish every little thing overnight, yet that you are using the actions needed to obtain where you intend to go. It’s all about documenting your objectives, advising on your own daily of what you wish to achieve, as well as getting there by means of persistency as well as willpower. Lots of guidelines as well as methods can be acquired at Our Technology Site, specifically in regard to aiding you to achieve your goals. Any person that mosts likely to this internet site can easily discover something from it, as well as despite the big quantity of info, it will certainly assist you in the long run.
I love the manner you have actually ended this blog post …
Just bookmarked this article as I have found it quite useful.
i am a certified Gleek and i really love the TV Show GLEE. Diana is very pretty-
I am extremely impressed with your writing skills and also with the layout on your blog. Is this a paid theme or did you customize it yourself? Anyway keep up the excellent quality writing, it’s rare to see a great blog like this one nowadays..
Outstanding short which post helped me alot. Give you thanks We seeking your own details?–.
https://www.tryarticles.com/
https://www.tryarticles.com/