Edit Distance
On te donne deux mots, word1 et word2. Une modification change word1 de l’une des trois façons suivantes : insérer une lettre n’importe où, supprimer une lettre ou remplacer une lettre par une autre. Retourne le nombre minimal de modifications nécessaires pour transformer word1 en word2.
Fonction
- word1string
- le mot que tu modifies
- word2string
- le mot « atteindre »
- Renvoieinteger
- le plus petit nombre d’insertions, de suppressions et de remplacements qui transforment word1 en word2
Contraintes
1 ≤ word1.length ≤ 5001 ≤ word2.length ≤ 500- Les deux mots ne contiennent que des lettres minuscules de l’alphabet anglais.
Exemples
- Entrée
- word1 = "spot"word2 = "stop"
- Sortie
- 2
- Explication
- Remplacez le p par un t et le t par un p :
spotdevientstot, puisstop. Une seule modification ne suffit pas, car les mots diffèrent en deux endroits et une insertion ou une suppression changerait la longueur.
- Entrée
- word1 = "garden"word2 = "ardent"
- Sortie
- 2
- Explication
- Supprimez le g pour obtenir
arden, puis insérez un t à la fin pour obtenirardent. Remplacer les lettres une par une coûterait 6, car les deux mots diffèrent à chaque position.
- Entrée
- word1 = "rain"word2 = "shine"
- Sortie
- 3
- Explication
- Remplace r par s et a par h, puis insère e. Deux modifications échouent : r et a ne figurent pas dans
shine, donc chacune nécessite une modification qui conserve la longueur, et le mot doit tout de même gagner une lettre.
Pour aller plus loin
Peux-tu également renvoyer une liste d’éditions la plus courte possible, en plus de leur nombre ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Regarde la dernière lettre de chaque mot. Si elles sont identiques, faut-il les modifier ? Si elles sont différentes, quelles modifications pourraient faire en sorte que les deux mots se terminent de la même façon ?
Il y a trois possibilités pour les dernières lettres : remplacer l’une par l’autre, supprimer la dernière lettre de
word1ou insérer la dernière lettre deword2. Chaque possibilité laisse le même problème sur des préfixes plus courts ; choisissez donc la moins coûteuse et ajoutez un.Stocke la réponse pour chaque paire de longueurs de préfixe
(i, j)dans un tableau. Un préfixe vide coûteisuppressions oujinsertions, ce qui remplit la première ligne et la première colonne. Remplis le reste ligne par ligne et lis la réponse dans la dernière cellule.
Solution
Les modifications interagissent : garden et ardent diffèrent aux six positions, et pourtant deux modifications suffisent. Regardez donc la dernière lettre de chaque mot. Soit les deux lettres sont identiques, soit l’une des trois modifications les rend identiques, et chaque choix laisse le même problème à résoudre sur des préfixes plus courts. Un tableau résout une seule fois chaque paire de préfixes.
Essaie les trois modifications avec la récursion
Correcte, mais ne termine pas sur les plus gros tests
Intuition
Soit edits(i, j) le nombre minimal de modifications nécessaires pour transformer le suffixe word1[i:] en word2[j:]. Si les premières lettres correspondent, conserve-les et avance les deux index : effectuer une modification sur une lettre identique n’est jamais utile. Sinon, ajoute 1 au coût minimal de trois appels : un remplacement avance les deux index, la suppression de word1[i] avance i, et l’insertion de word2[j] avance j. Quand l’un des mots est épuisé, chaque lettre restante dans l’autre coûte une modification.
Chaque différence déclenche trois appels : deux mots de 15 lettres sans aucune lettre en commun nécessitent environ 6.7 × 10^10 appels. Pourtant, il n’existe que (n+1) × (m+1) paires différentes (i, j), donc presque chaque appel répète un appel précédent.
Algorithme
- Si
idépasse la fin deword1, retournezm - j; sijdépasse la fin deword2, retournezn - i. - Si
word1[i] == word2[j], retournezedits(i+1, j+1). - Sinon, retournez
1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)). - La réponse est
edits(0, 0).
def minDistance(word1, word2):
n, m = len(word1), len(word2)
def edits(i, j):
# Fewest edits to turn word1[i:] into word2[j:]
if i == n:
return m - j # insert the rest of word2
if j == m:
return n - i # delete the rest of word1
if word1[i] == word2[j]:
return edits(i + 1, j + 1)
return 1 + min(edits(i + 1, j + 1), # replace word1[i] with word2[j]
edits(i + 1, j), # delete word1[i]
edits(i, j + 1)) # insert word2[j]
return edits(0, 0)Remplissez un tableau de préfixes
Intuition
Soit dp[i][j] le nombre minimal de modifications pour transformer les i premières lettres de word1 en les j premières lettres de word2. Si word1[i-1] est égal à word2[j-1], recopiez la valeur diagonale dp[i-1][j-1]. Sinon, ajoutez 1 au voisin le moins coûteux : la diagonale correspond à un remplacement, la cellule au-dessus à la suppression de word1[i-1], et la cellule à gauche à l’insertion de word2[j-1]. La ligne et la colonne de base ne contiennent pas des zéros : transformer i lettres en rien nécessite i suppressions, donc dp[i][0] = i, et de même dp[0][j] = j.
Pour transformer spot en stop, la dernière ligne est [4, 3, 2, 2, 2]. La cellule finale compare t et p ; sa diagonale (spo en sto) vaut 1 et ses autres voisines valent 2, donc la réponse est 1 + 1 = 2. Deux mots de 500 lettres remplissent 2.5 × 10^5 cellules, chacune en temps constant.
Algorithme
- Créez
dpavec(n+1) × (m+1)cellules,dp[i][0] = ietdp[0][j] = j. - Pour
ide 1 ànetjde 1 àm: siword1[i-1] == word2[j-1], définissezdp[i][j] = dp[i-1][j-1]. - Sinon, définissez
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). - Retournez
dp[n][m].
def minDistance(word1, word2):
n, m = len(word1), len(word2)
# dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i # delete all i letters
for j in range(m + 1):
dp[0][j] = j # insert all j letters
for i in range(1, n + 1):
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], # replace
dp[i - 1][j], # delete word1[i-1]
dp[i][j - 1]) # insert word2[j-1]
return dp[n][m]Conservez uniquement deux lignes
Intuition
La ligne i ne lit que la ligne i-1 et ses propres cellules à gauche, donc deux tableaux suffisent : prev pour la ligne terminée et cur pour la ligne que tu remplis. La diagonale est prev[j-1], la cellule du dessus est prev[j] et celle de gauche est cur[j-1]. La colonne de base se trouve maintenant dans la première entrée de chaque ligne, donc définis cur[0] = i avant de remplir la ligne i.
Transformer word2 en word1 nécessite le même nombre de modifications, puisque les insertions et les suppressions s’échangent. Échange les mots pour que les lignes suivent le plus court : min(n, m) + 1 nombres par ligne au lieu d’un tableau pouvant contenir jusqu’à 251,001 cellules, avec le même travail en O(n × m).
Algorithme
- Si
word2est plus long queword1, échange-les. - Définis
prev = [0, 1, ..., m]. - Pour chaque
ide 1 àn, définiscur[0] = iet rempliscur[1..m]selon la règle du tableau, en lisant la diagonale et la case au-dessus dansprevet la case à gauche danscur. Puis échangeprevetcur. - Renvoie
prev[m].
def minDistance(word1, word2):
if len(word2) > len(word1):
word1, word2 = word2, word1 # the rows run along the shorter word
m = len(word2)
# prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
prev = list(range(m + 1))
for i in range(1, len(word1) + 1):
cur = [i] + [0] * m # i letters into an empty prefix: delete them all
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j - 1], # replace
prev[j], # delete word1[i-1]
cur[j - 1]) # insert word2[j-1]
prev = cur
return prev[m]
Pièges et cas limites
- Remplir la ligne 0 et la colonne 0 avec des zéros, comme pour la plus longue sous-séquence commune. Transformer
abcen un préfixe vide coûte 3 suppressions, pas 0. - Oublier
cur[0] = idans la version à deux lignes. La première entrée conserve une valeur datant de deux lignes, et toutes les cellules suivantes sont incorrectes. - Compter une édition en cas de correspondance. Avec
1 + min(...)pour des lettres identiques, transformeraenacoûte 1. - Lire le voisin de gauche dans
prevau lieu decur. À gauche se trouve l’insertion deword2[j-1]dans la ligne courante. - Utiliser la récursion avec mémoïsation en Python sur des mots de 500 lettres. Les appels atteignent une profondeur de 1000, au-delà de la limite de récursion par défaut.
Questions fréquentes3
Quelle est la complexité temporelle de la distance d’édition ?
La solution par tableau remplit une cellule par paire de préfixes en temps constant : un temps de O(n × m) pour des longueurs n et m. Elle utilise O(n × m) de mémoire pour le tableau complet, ou O(min(n, m)) avec deux lignes. La récursion simple sans tableau a une complexité exponentielle.
La distance d’édition est-elle la même que la distance de Levenshtein ?
Cette version est la distance de Levenshtein : une insertion, une suppression et un remplacement coûtent chacun une unité. La distance d’édition est le nom générique. Seules les insertions et les suppressions donnent n + m - 2 × LCS, seuls les remplacements pour des chaînes de même longueur donnent la distance de Hamming, et l’ajout de l’échange de deux lettres voisines donne la version de Damerau.
Peut-on résoudre la distance d’édition avec un seul tableau ?
Oui. Remplis un tableau row sur place, de gauche à droite. Avant d’écraser row[j], il contient encore la valeur de la ligne précédente, et row[j-1] contient déjà celle de la ligne actuelle. Seule la diagonale est perdue ; enregistre donc l’ancienne valeur de row[j] dans une variable et utilise-la comme diagonale pour j + 1.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def minDistance(word1, word2):
# Écrivez le code iciTest #1
Test #2
Test #3
Arguments
word1 = "spot" word2 = "stop"
Résultat attendu
2