You can do all Levenshtein edits while looking up in a (minimised, acyclic) FSA, which is fairly easy to implement[1], but means instead of having one FSA-state

You can do all Levenshtein edits while looking up in a (minimised, acyclic) FSA, which is fairly easy to implement[1], but means instead of having one FSA-state per index in the word as you look it up, you now have a set of states (each with their N_edits counter). [1] If you want transpositions to count as a single edit you need some hackery though.