Levenshtein distance (ou “distância de edição”) é uma métrica que mede o quão diferentes duas strings são, contando o número mínimo de operações necessárias para transformar uma string na outra.
As três operações permitidas são:
- Inserção de um caractere
- Remoção de um caractere
- Substituição de um caractere por outro
Exemplo:
Transformar "gato" em "rato":
- Substituir
gporr→ 1 operação
Distância = 1
Transformar "kitten" em "sitting":
- kitten → sitten (substituir k por s)
- sitten → sittin (substituir e por i)
- sittin → sitting (inserir g)
Distância = 3
Para que serve?
É muito usada em situações como correção ortográfica (sugerir palavras parecidas com um erro de digitação), busca aproximada de strings, detecção de plágio, bioinformática (comparar sequências de DNA), e sistemas de auto-completar.
Complexidade:
O algoritmo clássico usa programação dinâmica e tem complexidade O(m × n), onde m e n são os tamanhos das duas strings.