Distance d’édition étape par étape
Insérer, supprimer et remplacer pour transformer
Distance d’édition étape par étape est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Ce que mesure la distance d'édition
La distance d'édition est le nombre minimal de modifications d'un seul caractère nécessaires pour transformer une chaîne en une autre. Elle mesure la différence réelle entre deux mots.
Les trois opérations
Vous pouvez insérer, supprimer ou remplacer un caractère par modification. Dans le problème standard, chaque opération coûte exactement une unité.
Définir l'état
Soit dp[i][j] le nombre de modifications nécessaires pour transformer les i premiers caractères de A en les j premiers caractères de B.
Correspondance gratuite
Si les caractères actuels correspondent déjà, aucune modification n'est nécessaire. Reportez simplement la valeur de la diagonale.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Sinon, payez une unité
Lorsque les caractères diffèrent, prenez le voisin le moins coûteux et ajoutez une modification. Ce minimum plus un couvre les trois opérations.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Quel voisin correspond à quelle opération ?
La cellule du dessus correspond à une suppression, celle de gauche à une insertion et la diagonale à un remplacement. Le minimum choisit simplement la moins coûteuse.
Cas de base avec une chaîne vide
Transformer une chaîne de longueur i en chaîne vide nécessite i suppressions. Remplissez donc la première ligne et la colonne avec 0, 1, 2, et ainsi de suite.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jDimensionner le tableau
Utilisez une grille de n+1 par m+1 afin que les préfixes vides disposent de leur propre ligne et colonne. Ce remplissage simplifie les boucles.
dp = [[0] * (m+1) for _ in range(n+1)]Remplir dans l'ordre
Parcourez i et j dans l'ordre croissant à partir de 1. Chaque cellule dépend uniquement de voisins déjà remplis, au-dessus, à gauche et en diagonale.
for i in range(1, n+1):
for j in range(1, m+1):
...Lire la distance
Le nombre minimal de modifications se trouve dans le coin. Votre réponse est dp[n][m] une fois le tableau terminé.
distance = dp[n][m]Coût et variantes
Le calcul s'effectue en temps O(n fois m). Les problèmes réels peuvent attribuer des coûts différents à chaque opération, mais la même récurrence reste valable.
Vérification rapide
Les caractères A[i-1] et B[j-1] diffèrent. Quelle récurrence donne la distance d'édition ?
Récapitulatif : distance d'édition
Une correspondance consiste à reporter la diagonale ; une différence consiste à ajouter 1 au minimum des trois voisins. Initialisez les bords, puis lisez dp[n][m]. ✏️
Apprends Python avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 30
- Leçons
- 120
Questions Fréquemment Posées
La leçon « Distance d’édition étape par étape » est-elle gratuite ?
Oui — le texte complet de « Distance d’édition étape par étape » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Distance d’édition étape par étape » ?
Insérer, supprimer et remplacer pour transformer Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Distance d’édition étape par étape » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Compter les chemins sur une grille
- Somme minimale d’un chemin avec obstacles
- Plus longue sous-séquence commune
- Distance d’édition étape par étape