Distance d'Édition (Levenshtein)
Algorithmique classique
Enonce
Calculer la distance d'édition (Levenshtein) entre deux chaînes : le nombre minimal d'insertions, suppressions ou substitutions pour transformer a en b.
Signature attendue
def distance_edition(a: str, b: str) -> int:Exemples
distance_edition("kitten", "sitting")→3distance_edition("abc", "abc")→0distance_edition("", "hello")→5
📖 Rappel de cours
Le nombre minimal d'insertions, suppressions ou substitutions pour passer d'un mot à l'autre. Chaque case du tableau se déduit de ses trois voisines.
⚠ Le piège : Les bords ne sont pas nuls : passer d'un mot vide à un mot de k lettres coûte k. Initialiser la première ligne et la première colonne à 0 fausse tout le tableau.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Fibonacci par Programmation Dynamique
- Sac à Dos 0/1
- Plus Longue Sous-séquence Commune (LCS)
- Montée d'Escalier
- Recherche Dichotomique Itérative
- Première Occurrence par Dichotomie
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.