Re:A spellchecker used to be a major feat of software engine...
by mattkrause on Thursday December 03, 2020 @07:40PM
(#25297548)
Can't edit distance be computed in O(mn) time/space with dynamic programming?
[ Parent
| on HN ]
Re:A spellchecker used to be a major feat of software engine...
by zingermc on Thursday December 03, 2020 @09:24PM
(#25298212)
Yes, 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.