Prépa Code Connexion Inscription

La distance de Levenshtein (ou distance d'edition) entre deux chaines de caracteres s1 et s2 est le nombre minimal d'operations elementaires pour transformer s1 en s2. Les operations autorisees sont :

• Insertion d'un caractere (cout 1)
• Suppression d'un caractere (cout 1)
• Substitution d'un caractere par un autre (cout 1)

On note d(i, j) la distance de Levenshtein entre les i premiers caracteres de s1 et les j premiers caracteres de s2. La relation de recurrence est :

• Si min(i, j) = 0 : d(i, j) = max(i, j)
• Si s1[i-1] == s2[j-1] : d(i, j) = d(i-1, j-1)
• Sinon : d(i, j) = 1 + min(d(i-1, j), d(i, j-1), d(i-1, j-1))

Ecrire une fonction levenshtein(s1, s2) qui calcule cette distance par programmation dynamique (approche bottom-up avec un tableau).