Edit Distance

Q: Quelle est la complexité temporelle de la distance d’édition ?

La solution par tableau s’exécute en O(n × m) , où n et m sont les deux longueurs, car elle remplit une cellule par paire de préfixes avec un travail constant. 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 est exponentielle.

Q: Comment obtenir la liste des modifications, et pas seulement leur nombre ?

Gardez le tableau complet et remontez à partir de dp[n][m] . Si les lettres correspondent, avancez en diagonale sans effectuer de modification. Sinon, passez au voisin dont la valeur est inférieure de un : la diagonale correspond à un remplacement, le haut à une suppression et la gauche à une insertion. Arrêtez-vous à dp[0][0] et lisez les modifications à l’envers. La version à deux lignes ne peut pas le faire à elle seule, car elle a supprimé les lignes précédentes.

Q: La distance d’édition peut-elle être résolue 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à la valeur de la ligne actuelle. La seule valeur que tu perds est celle de la diagonale, alors conserve-la dans une variable : enregistre l’ancienne valeur de row[j] avant d’écrire, et utilise-la comme valeur diagonale pour j + 1 .

DifficileProgrammation dynamique

+10

Vous recevez deux mots, word1 et word2. Une modification change word1 d’une des trois façons suivantes : insérer une lettre n’importe où, supprimer une lettre ou remplacer une lettre par une autre. Retournez le nombre minimal de modifications nécessaires pour transformer word1 en word2.

Fonction

minDistance(word1: string, word2: string) → integer

word1string: le mot que vous modifiez
word2string: le mot atteindre
Renvoieinteger: le moins d’insertions, de suppressions et de remplacements nécessaires pour transformer word1 en word2

Contraintes

1 ≤ word1.length ≤ 500
1 ≤ 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: Remplace le p par un t et le t par un p : spot devient stot, puis stop. Une seule modification ne suffit pas, car les mots diffèrent à deux endroits et une insertion ou une suppression modifierait 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 obtenir ardent. Remplacer chaque lettre coûterait 6, car les deux mots diffèrent à chaque position.

Entrée: word1 = "rain"word2 = "shine"
Sortie: 3
Explication: Remplacez r par s et a par h pour obtenir shin, puis insérez e. Deux modifications ne suffisent pas : r et a n’apparaissent pas dans shine, donc chacune nécessite une modification qui n’allonge pas le mot, et le mot doit encore gagner une lettre.

+21 tests cachés à la soumission

Pour aller plus loin

Peux-tu aussi renvoyer une liste des modifications les plus courtes, et pas seulement leur nombre ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Les modifications interagissent, donc vous ne pouvez pas corriger les mots position par position : garden et ardent diffèrent aux six positions, pourtant deux modifications suffisent une fois que le g est supprimé et que tout se décale vers la gauche. L’idée qui permet de résoudre le problème consiste à ne regarder que la dernière lettre de chaque mot. Soit les deux lettres sont déjà identiques, soit l’une des trois modifications possibles les rend identiques, et chaque choix laisse le même problème sur des préfixes plus courts. Un tableau de réponses (n+1) × (m+1) résout une fois pour toutes chaque paire de préfixes, et deux de ses lignes suffisent.

Essayez les trois modifications avec la récursivité

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:]. Regardons les premières lettres des deux suffixes. Si elles sont égales, conservons-les et avançons les deux indices : une lettre identique n’a jamais besoin d’être modifiée, et tout plan qui dépense une modification pour elle peut être remplacé par un plan qui la conserve sans être plus long.

Si elles diffèrent, une modification doit traiter word1[i] ou produire word2[j], et il existe exactement trois possibilités. Remplacer word1[i] par word2[j] et avancer les deux indices : edits(i+1, j+1). Supprimer word1[i] et avancer uniquement i : edits(i+1, j). Insérer word2[j] devant cette lettre et avancer uniquement j : edits(i, j+1). La réponse est égale à 1 plus le coût minimal des trois possibilités. Lorsque word1 est épuisé, insérer le reste de word2, ce qui coûte m - j ; lorsque word2 est épuisé, supprimer le reste de word1, ce qui coûte n - i.

C’est lent, car chaque différence déclenche trois appels. Pour deux mots de 15 lettres sans aucune lettre en commun, cela représente environ 6.7 × 10^10 appels, et les grands tests comptent 500 lettres chacun. Pourtant, il n’existe que (n+1) × (m+1) paires (i, j) différentes, donc presque chaque appel répète un appel déjà effectué.

Algorithme

Écris edits(i, j) pour les suffixes commençant à i et j.
Si i dépasse la fin de word1, retourne m - j ; si j dépasse la fin de word2, retourne n - i.
Si word1[i] == word2[j], retourne edits(i+1, j+1).
Sinon, retourne 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)) pour le remplacement, la suppression et l'insertion.
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 des préfixes

Intuition

État. Soit dp[i][j] le nombre minimal de modifications nécessaires pour transformer les i premières lettres de word1 en les j premières lettres de word2. L’indice 0 représente un préfixe vide.

Transitions. Comparez les dernières lettres des deux préfixes, word1[i-1] et word2[j-1]. Si elles sont égales, conservez-les : dp[i][j] = dp[i-1][j-1], la cellule située en diagonale vers le haut et la gauche. Sinon, effectuez une modification et choisissez la valeur minimale parmi trois cellules voisines. La diagonale dp[i-1][j-1] signifie remplacer word1[i-1] par word2[j-1]. La cellule au-dessus, dp[i-1][j], signifie supprimer word1[i-1]. La cellule à gauche, dp[i][j-1], signifie insérer word2[j-1] à la fin.

Ligne et colonne de base. Contrairement à de nombreux problèmes de tableaux, elles ne contiennent pas des zéros. Transformer i lettres en un préfixe vide nécessite i suppressions, donc dp[i][0] = i. Construire j lettres à partir de rien nécessite j insertions, donc dp[0][j] = j. Chaque cellule lit la cellule au-dessus, celle à sa gauche et celle en diagonale ; en remplissant ligne par ligne, de gauche à droite, ces valeurs sont donc déjà calculées. La réponse est dp[n][m].

Voici le tableau pour transformer spot en stop, avec les préfixes "", s, st, sto, stop comme colonnes. La ligne "" est [0, 1, 2, 3, 4], la ligne s est [1, 0, 1, 2, 3], la ligne sp est [2, 1, 1, 2, 2], la ligne spo est [3, 2, 2, 1, 2] et la ligne spot est [4, 3, 2, 2, 2]. Examinons quelques cellules. s comparé à s correspond, donc la valeur diagonale 0 est copiée. sp comparé à st ne correspond pas : ses cellules voisines valent 0 en diagonale, 1 au-dessus et 1 à gauche ; sa valeur est donc 1 + 0 = 1, soit un remplacement. spo comparé à sto correspond pour la lettre o et copie cette valeur 1. La dernière cellule, spot comparé à stop, compare t et p : ses cellules voisines valent 1, 2 et 2 ; la réponse est donc 1 + 1 = 2.

Le tableau comporte (n+1) × (m+1) cellules, chacune nécessitant un nombre constant d’opérations, soit environ 2.5 × 10^5 étapes pour deux mots de 500 lettres. Une récursion avec mémoïsation remplit les mêmes cellules, mais elle peut atteindre une profondeur de n + m appels, ce qui dépasse la limite par défaut de 1000 de Python.

Algorithme

Crée un tableau dp de (n+1) × (m+1) cellules.
Définis dp[i][0] = i pour chaque i et dp[0][j] = j pour chaque j.
Pour i de 1 à n et j de 1 à m, si word1[i-1] == word2[j-1], définis dp[i][j] = dp[i-1][j-1].
Sinon, définis dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Renvoie 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]

Ne conserver que deux lignes

Intuition

La ligne i ne lit que la ligne i-1 et ses propres cellules à gauche. Une fois une ligne terminée, les lignes situées au-dessus ne sont plus jamais lues. Gardez deux tableaux : prev pour la ligne terminée et cur pour la ligne que vous remplissez, puis échangez-les après chaque ligne. Les transitions ne changent pas : 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 ne disparaît pas. Elle se trouve désormais dans la première entrée de chaque ligne ; définissez donc cur[0] = i avant de remplir la ligne i. La ligne 0 commence par [0, 1, 2, ..., m], la ligne de base.

Transformer word2 en word1 nécessite le même nombre de modifications, car chaque insertion devient une suppression et chaque suppression une insertion. Vous pouvez donc échanger les mots et faire défiler les lignes le long du plus court. Chaque ligne contient alors min(n, m) + 1 nombres au lieu d’une table pouvant contenir jusqu’à 251,001 cellules, et le travail reste en O(n × m).

Algorithme

Si word2 est plus long que word1, échange-les.
Définis prev = [0, 1, ..., m], où m est la longueur la plus courte.
Pour chaque i de 1 à n, définis cur[0] = i, puis remplis cur[1..m] en appliquant la même règle, en lisant la diagonale et la valeur du dessus dans prev, et la valeur de gauche dans cur.
Échange prev et cur.
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

La récurrence est courte, donc la plupart des bogues se trouvent dans les cas de base ou dans le voisin lu.

Remplir la ligne 0 et la colonne 0 avec des zéros, comme pour la plus longue sous-séquence commune. Transformer abc en un préfixe vide coûte 3 suppressions, et non 0 ; dp[i][0] doit donc être égal à i et dp[0][j] doit être égal à j.
Oublier cur[0] = i dans la version à deux lignes. La première entrée conserve une valeur datant de deux lignes auparavant, et toutes les cellules qui la suivent sont incorrectes.
Compter une modification lorsqu’il y a correspondance. dp[i][j] = 1 + min(...) pour des lettres égales fait que transformer a en a coûte 1. En cas de correspondance, recopiez la valeur diagonale.
Lire le voisin de gauche dans prev au lieu de cur. La valeur de gauche appartient à la ligne actuelle : elle correspond à l’insertion de word2[j-1] après que word1[:i] a déjà été transformé en word2[:j-1].
Comparer les positions une par une. Compter les endroits où les mots diffèrent ne tient pas compte des insertions et des suppressions : cela donne 6 pour garden et ardent, alors que la réponse est 2.
Utiliser la mémorisation avec une récursion sur des mots de 500 lettres. La profondeur des appels atteint 1000, ce qui correspond à la limite par défaut de Python.

Questions fréquentes4

Quelle est la complexité temporelle de la distance d’édition ?

La solution par tableau s’exécute en O(n × m), où n et m sont les deux longueurs, car elle remplit une cellule par paire de préfixes avec un travail constant. 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 est exponentielle.

La distance d’édition est-elle la même chose que la distance de Levenshtein ?

Oui, cette version est la distance de Levenshtein : les insertions, suppressions et remplacements coûtent chacun une unité. La distance d’édition est le nom de la famille. D’autres variantes autorisent moins ou plus d’opérations : les insertions et suppressions seules donnent n + m - 2 × LCS, les remplacements seuls 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 variante de Damerau.

Comment obtenir la liste des modifications, et pas seulement leur nombre ?

Gardez le tableau complet et remontez à partir de dp[n][m]. Si les lettres correspondent, avancez en diagonale sans effectuer de modification. Sinon, passez au voisin dont la valeur est inférieure de un : la diagonale correspond à un remplacement, le haut à une suppression et la gauche à une insertion. Arrêtez-vous à dp[0][0] et lisez les modifications à l’envers. La version à deux lignes ne peut pas le faire à elle seule, car elle a supprimé les lignes précédentes.

La distance d’édition peut-elle être résolue 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à la valeur de la ligne actuelle. La seule valeur que tu perds est celle de la diagonale, alors conserve-la dans une variable : enregistre l’ancienne valeur de row[j] avant d’écrire, et utilise-la comme valeur diagonale pour j + 1.

Python

def minDistance(word1, word2):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

word1 = "spot"
word2 = "stop"

Attendu

Edit Distance

Fonction

Contraintes

Exemples

Indices

Solution

Essayez les trois modifications avec la récursivité

Remplissez un tableau des préfixes

Ne conserver que deux lignes

Pièges et cas limites

Questions fréquentes4

Problèmes similaires