Calculer la distance d'édition de Levenshtein

Implémenter l'algorithme de distance de Levenshtein par programmation dynamique pour calculer le nombre minimal d'insertions, suppressions et substitutions permettant de transformer une chaîne en une autre.

60 minPublié le 20 mai 2026Proposé par Anonyme

Défi

// Lisez attentivement, codez sur votre machine

Énoncé

Le programme lit deux chaînes de caractères (une par ligne) et affiche leur distance de Levenshtein : le nombre minimal d'opérations élémentaires (insertion d'un caractère, suppression d'un caractère, substitution d'un caractère par un autre) pour transformer la première chaîne en la seconde. L'algorithme classique utilise une matrice (N+1) × (M+1) de programmation dynamique.

Contraintes

Chaque chaîne contient entre 0 et 1 000 caractères ASCII imprimables.
La distance entre deux chaînes vides est 0.
La distance entre une chaîne vide et une chaîne de longueur L est L.
La comparaison est sensible à la casse.
Solution réalisable dans tout langage généraliste avec sa seule bibliothèque standard.

Exemple

Entrée :
kitten
sitting

Sortie :
3

Entrée :
sunday
saturday

Sortie :
3

Espace solution

Proposer une solution

Connectez-vous ou créez un compte pour envoyer votre code (aucune exécution côté serveur — on stocke juste le texte pour la communauté).

Se connecter Créer un compte

Défi précédentDétecter les doublons dans une liste d'entiers Défi suivant Distance de Manhattan entre deux points entiers

// À garder en tête

D'abord, faire marcher
On ne cherche pas à optimiser : d'abord, on fait marcher le truc. Optimiser vient ensuite — et ça aussi, ça s'apprend. (Si un défi porte sur l'optimisation, son énoncé le précise.)
Pas de mauvaise réponse
Il n'y a pas de mauvaise réponse à un défi. Le but, c'est de le faire. Ce qui compte, c'est de s'entraîner.
Trop dur ? Au suivant
Un défi te résiste ? N'hésite pas à en prendre un autre. Ils seront encore là demain.