2 ms·
Can't edit distance be computed in O(mn) time/space with dynamic programming?
by mattkrause 6y ago
Can't edit distance be computed in O(mn) time/space with dynamic programming?
- zingermc 6y agoYes, at least for Levenshtein-style edits (substitution, insertion, deletion). Although, I suppose a spell checker algorithm would be O(mnd) where d is the size of the dictionary, because it needs to compute O(mn) edit distance for each of the dictionary words.