2 ms·
Hmm true - very good point. Worth noting that for short strings this is unlikely to matter. There is [1], titled APPROXIMATING EDIT DISTANCE IN NEAR-LINEAR TI
by nl 11y ago
Hmm true - very good point.
Worth noting that for short strings this is unlikely to matter.
There is [1], titled APPROXIMATING EDIT DISTANCE IN NEAR-LINEAR TIME. Wikipedia also has a reference[2] for better time complexity versions.
I haven't explored these though.
[1] http://www.mit.edu/~andoni/papers/compEdit.pdf http://www.mit.edu/~andoni/papers/compEdit.pdf
[2] https://en.wikipedia.org/wiki/Edit_distance#Improved_algorithms https://en.wikipedia.org/wiki/Edit_distance#Improved_algorit...