Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Edit Distance

Given two strings, find the minimum number of operations required to convert string-1 to string-2 using three operators: replace(i), delete(i) and insert(i)

Solution: Find the longest common subsequence and store the indexes of matching characters for each string in a boolean array.

Example:
For strings like ABCDE and BAFDE, maximum subsequences are BDE and ADE

Choose any one, say BDE. The match-arrays would be:
01011 for ABCDE
10011 for BAFDE

Iterate over both the arrays till you find first 1

All characters from start position to this position would be different.

So replace as many characters can be replaced and delete/insert the remaining ones.

Now move to second 1 on both the strings.

Note: It does not matter which maximum subsequence you choose (if there are more than 1 max subsequences with equal length) because the number of non-matching/missing/extra characters are the same. And any kind of mismatch takes one operation only to correct.

So, all the maximum subsequences will give the same edit-distance.

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: