Distance d'Édition (Levenshtein)

Programmation dynamique 2D sur deux chaînes

Exercice Avancé · Algorithmique · prepa scientifique et economique (CPGE)

Enonce

Implémenter distance_edition(s, t) qui renvoie la distance de Levenshtein entre les deux chaînes en utilisant la programmation dynamique.

Exemples : distance_edition("chat", "chien") == 3 (substitution de a→i, substitution de t→e, insertion de n).

⚠ Contrainte : DP bottom-up avec un tableau 2D. Complexité $O(|s| \cdot |t|)$.

Signature attendue

def distance_edition(s: str, t: str) -> int:

Exemples

distance_edition("chat", "chien") → 3
distance_edition("", "") → 0
distance_edition("abc", "") → 3

📖 Rappel de cours

La distance de Levenshtein entre deux chaînes s et t est le nombre minimum d'opérations élémentaires pour transformer s en t, où chaque opération vaut $1$ :

insertion d'un caractère
suppression d'un caractère
substitution d'un caractère par un autre

Récurrence :

Soit $D(i, j)$ la distance entre les préfixes $s[0..i]$ et $t[0..j]$.

$D(i, 0) = i$ (supprimer $i$ caractères)
$D(0, j) = j$ (insérer $j$ caractères)
Si $s[i-1] = t[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))$

Applications : correcteurs orthographiques, bio-informatique (alignement d'ADN), diff de fichiers.

← Exercices d'algorithmique en Python — tris, dichotomie, récursivité

Exercices du meme theme

La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.