= Solution
Use unit-cost insertion, deletion and substitution of one symbol. Their minimum total cost is the <edit distance>. Let $D[i,j]$ be the <edit distance> between the first $i$ symbols of the first sequence and the first $j$ of the second. Initialize $D[i,0]=i$ and $D[0,j]=j$. For $i,j>0$ compute
$$
D[i,j]=\min\left\{D[i-1,j]+1,\ D[i,j-1]+1,\ D[i-1,j-1]+[x_i\ne y_j]\right\}.
$$
The cases delete the final source symbol, insert the final target symbol, or align the two final symbols, paying one for substitution and zero for a match. Every optimal alignment ends in one of these cases, and each case extends a valid shorter alignment. <Induction> on $i+j$ proves the <dynamic programming> recurrence correct.
Fill rows or columns in increasing order so every dependency is already available. There are $(m+1)(n+1)$ entries with constant work per interior entry: \b[$O(mn)$ <running time>] for nonempty sequences, or $O((m+1)(n+1))$ including the boundary cases. The full table has <space complexity> $O(mn)$; two rows give $O(n)$ <auxiliary space> when only the distance is wanted. Predecessor choices in the full table recover an optimal edit sequence.
Back to article page
