Edit Distance
Given
two strings, find the minimum number of operations required to
convert string1 to string2 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 matcharrays 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
nonmatching/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 editdistance.
