Wagner-Fischer Algorithm
A dynamic-programming algorithm that computes the minimum edit cost between two strings using insertion, deletion, and substitution operations.
Wagner-Fischer is a useful reference implementation for edit distance: each DP cell stores the minimum transformation cost between two prefixes and is updated from insertion, deletion, and substitution candidates.
The standard running time is O(m*n). If only the distance is needed, memory can be reduced to O(min(m,n)); reconstructing an edit script requires backpointers or another reconstruction strategy.
Production Note
When only matches below a threshold matter, filling the complete matrix can be wasteful. Banded/Ukkonen-style bounds and early termination can reduce CPU substantially. For Unicode text, the chosen unit - byte, code point, or grapheme cluster - also changes the meaning of the distance.
Source
- https://dl.acm.org/doi/10.1145/321796.321811