Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 7 / a / 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$ computeThe 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: $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.