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.
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
Now move to second 1 on both the strings.
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.
all the maximum subsequences will give the same edit-distance.