Make delicious recipes!

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:

Facebook comments:

Site Owner: Sachin Goyal