No livro Projeto de Algoritmos do Nivio Ziviani tem um algorítmo chamado Shift-And-Aproximado que eu acho muito interessante. Você escolhe o número de diferenças aceitáveis, entre inclusão, remoção ou alteração de caracteres, e manda rodar.
O código dele é bem pequeno e simples de implementar, mas a idéia é bem legal pois ele na verdade cria umas máscaras de bits e fica fazendo um monte de operação bitwise para simular um autônomo de comparação.
E o custo dele é muito bom por se aproveitar do paralelismo de bits. No caso médio ele é linear, de ordem O(kn) onde k é o número de diferenças aceitáveis e n o tamanho do texto.
Esse algoritimo do shift é muito útil… procura sobre ele q vc resolve seu problema… + jah vou te adiantando… se vc colocar uma tolerância maior do que 1, vc consegue palavras q não tem nada a ver com o digitado… + beleza…