Prépa Code Connexion Inscription

Écrire une fonction distance : string -> string -> int qui renvoie la distance d'édition (ou distance de Levenshtein) entre deux chaînes.

La distance d'édition est le nombre minimum d'opérations élémentaires pour transformer une chaîne en l'autre, chaque opération ayant un coût de 1 : - insertion d'un caractère, - suppression d'un caractère, - substitution d'un caractère par un autre.

Par exemple, distance "chat" "chien" = 3 (substituer 'a' par 'i', substituer 't' par 'e', insérer 'n').

Cas particuliers : - distance "" "" = 0, - distance s "" = String.length s, - distance "" s = String.length s.

On utilisera la programmation dynamique avec un tableau 2D.