Edit distance
The edit distance between S1 and S2 is the minimum number of deletions, insertions and substitutions needed to transform S1 to S2.
|S1|=m, |S2|=n
D(i,j) is the edit distance between S1[1..i] and S2[1..j].
Recurrence relation:
basis:
Previous slide
Next slide
Back to first slide
View graphic version