Edit distance between two symbols

Question

A reference-data pipeline needs to fuzzy-match ticker symbols across vendors ("BRK.B" vs "BRKB", "VOD LN" vs "VOD.L"). The workhorse metric is Levenshtein distance: the minimum number of single-character insertions, deletions, or substitutions turning string a into string b.

a = "horse", b = "ros"
-> 3            # horse -> rorse -> rose -> ros

Compute the edit distance. Target $O(|a|\cdot|b|)$ time, and can you do it in $O(\min(|a|,|b|))$ space?

Accepted Answer

Let D[i][j] be the distance between the first i characters of a and the first j of b. Boundaries: D[i][0] = i (delete everything), D[0][j] = j (insert everything). For the general cell, condition on how the last characters are handled: D[i][j] = \begin{cases} D[i-1][j-1] & ai = bj \ 1 + \min\big(D[i-1][j-1],\ D[i-1][j],\ D[i][j-1]\big) & 	ext{otherwise} \end{cases} where the three options are substitute, delete from a, and insert into a. Each row depends only on the previous row, so keep two rows instead of the full table: For "horse" vs "ros" the final row evaluates to distance 3, matching…

Edit distance between two symbols

Your answer

More Coding questions