Coding Interview Prep · Leçon

Distance d’édition (Levenshtein)

Distance d’édition (Levenshtein) est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.

Le problème de la distance d’édition

La distance d’édition (distance de Levenshtein, LeetCode 72) demande : quel est le nombre minimal d’opérations d’insertion, de suppression ou de remplacement nécessaires pour transformer une chaîne en une autre ? Par exemple, pour transformer 'horse' en 'ros' : remplacer 'h'→'r' (horse→rorse), supprimer 'r' (rorse→rose), supprimer 'e' (rose→ros) — 3 opérations. La distance d’édition est fondamentale pour les correcteurs orthographiques, l’alignement de l’ADN et l’appariement approximatif.

# Allowed operations:
# Insert: 'abc' → 'abXc' (insert X)
# Delete: 'abc' → 'ac' (delete b)
# Replace: 'abc' → 'aXc' (replace b with X)

# horse → ros: 3 operations
# 1. horse → rorse (replace h with r)
# 2. rorse → rose  (delete r at index 1)
# 3. rose  → ros   (delete e)
print('Edit distance horse→ros: 3')
print('Edit distance intention→execution: 5')

État DP et relation de récurrence

Définissez dp[i][j] comme la distance d’édition minimale entre word1[:i] et word2[:j]. Si word1[i-1] == word2[j-1], aucune opération n’est nécessaire : dp[i][j] = dp[i-1][j-1]. Sinon, prenez le minimum des trois opérations suivantes : insérer dp[i][j-1] + 1, supprimer dp[i-1][j] + 1, remplacer dp[i-1][j-1] + 1. Cas de base : dp[i][0] = i (supprimer tous les caractères de word1) et dp[0][j] = j (insérer tous les caractères de word2).

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    # Base cases
    for i in range(m+1): dp[i][0] = i  # delete all of word1
    for j in range(n+1): dp[0][j] = j  # insert all of word2
    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # no cost
            else:
                dp[i][j] = 1 + min(
                    dp[i][j-1],    # insert
                    dp[i-1][j],    # delete
                    dp[i-1][j-1]   # replace
                )
    return dp[m][n]

print(edit_distance('horse', 'ros'))          # 3
print(edit_distance('intention', 'execution')) # 5

Comprendre les trois opérations

Les trois opérations correspondent directement à des déplacements dans la table DP : remplacer dp[i-1][j-1]+1 — les deux caractères correspondent, mais nous payons un coût. Supprimer de word1 dp[i-1][j]+1 — retirer un caractère de word1 (se déplacer vers le haut dans la table). Insérer dans word1 dp[i][j-1]+1 — insérer un caractère pour le faire correspondre à word2 (se déplacer vers la gauche). Le minimum des trois donne le chemin optimal des modifications.

# Visualise the DP table for 'cat' → 'cut'
# dp[i][j] = min edits for word1[:i] vs word2[:j]

word1, word2 = 'cat', 'cut'
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
    for j in range(1, n+1):
        if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
        else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
print('  ', ' '.join(' '+word2))
for i, row in enumerate(dp):
    print((' ' if i==0 else word1[i-1]), row)

Optimisation de l’espace en O(n)

La distance d’édition nécessite uniquement la ligne actuelle et la ligne précédente. Utilisez un tableau 1D de taille n+1 et suivez séparément la valeur diagonal (dp[i-1][j-1]) avant la mise à jour de chaque cellule. Parcourez la ligne de gauche à droite : temp = dp[j] (ancienne valeur = dp[i-1][j]), puis mettez à jour dp[j] en utilisant dp[j] (suppression), dp[j-1] (insertion) et diagonal (remplacement).

def edit_distance_1d(word1, word2):
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))  # initial row: 0,1,2,...,n
    for i in range(1, m + 1):
        diag = dp[0]       # dp[i-1][0]
        dp[0] = i          # dp[i][0] = i
        for j in range(1, n + 1):
            temp = dp[j]   # dp[i-1][j] before overwrite
            if word1[i-1] == word2[j-1]:
                dp[j] = diag
            else:
                dp[j] = 1 + min(dp[j],     # delete
                                dp[j-1],   # insert
                                diag)      # replace
            diag = temp
    return dp[n]

print(edit_distance_1d('horse', 'ros'))          # 3
print(edit_distance_1d('intention', 'execution')) # 5

Reconstruction des opérations d’édition

Pour reconstruire la séquence réelle de modifications, remontez dans la table DP à partir de (m, n). À chaque cellule : si word1[i-1] == word2[j-1], déplacez-vous en diagonale (aucune opération). Sinon, déterminez lequel des trois voisins a fourni le minimum et enregistrez l’opération correspondante. Le script de modifications est ainsi produit dans l’ordre inverse ; inversez-le pour obtenir la réponse finale.

def edit_ops(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0]=i
    for j in range(n+1): dp[0][j]=j
    for i in range(1,m+1):
        for j in range(1,n+1):
            if word1[i-1]==word2[j-1]: dp[i][j]=dp[i-1][j-1]
            else: dp[i][j]=1+min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])
    ops, i, j = [], m, n
    while i>0 or j>0:
        if i>0 and j>0 and word1[i-1]==word2[j-1]:
            i-=1; j-=1
        elif j>0 and (i==0 or dp[i][j-1]<=dp[i-1][j] and dp[i][j-1]<=dp[i-1][j-1]):
            ops.append(f'Insert {word2[j-1]} at pos {i}'); j-=1
        elif i>0 and (j==0 or dp[i-1][j]<=dp[i][j-1] and dp[i-1][j]<=dp[i-1][j-1]):
            ops.append(f'Delete {word1[i-1]} at pos {i-1}'); i-=1
        else:
            ops.append(f'Replace {word1[i-1]} with {word2[j-1]}'); i-=1; j-=1
    return list(reversed(ops))

for op in edit_ops('horse', 'ros'): print(op)

Vérification d’une distance d’une seule modification

Un problème d’entretien plus simple consiste à déterminer si deux chaînes sont séparées par exactement une modification. Cela s’effectue en O(n), sans DP. Parcourez les deux chaînes simultanément. En cas de non-correspondance, essayez les trois opérations (ignorer un caractère dans s1, ignorer un caractère dans s2, ignorer les deux) et vérifiez si les parties restantes sont identiques. Si deux non-correspondances se produisent, renvoyez False. Cette approche gloutonne évite le DP complet en O(mn) lorsque vous devez seulement savoir si la distance est ≤ 1.

def is_one_edit_distance(s, t):
    m, n = len(s), len(t)
    if abs(m - n) > 1: return False
    if m > n: return is_one_edit_distance(t, s)  # ensure m <= n
    for i in range(m):
        if s[i] != t[i]:
            if m == n:
                return s[i+1:] == t[i+1:]   # replace
            else:
                return s[i:] == t[i+1:]     # insert into s (delete from t)
    return m + 1 == n  # all matched, lengths differ by 1

print(is_one_edit_distance('ab', 'acb'))   # True (insert c)
print(is_one_edit_distance('ab', 'ab'))    # False (zero edits)
print(is_one_edit_distance('ab', 'abc'))   # True (append c)
print(is_one_edit_distance('ab', 'xyz'))   # False

Comparaison entre la distance d’édition et le LCS

La distance d’édition (avec les trois opérations) et le LCS offrent deux points de vue complémentaires sur la similarité des chaînes. La distance d’édition compte la différence ; le LCS compte la similarité. Lorsque seules les insertions et les suppressions sont autorisées (sans remplacement), distance d’édition = m + n - 2×LCS. Lorsque les substitutions sont autorisées, le DP est légèrement différent : la diagonale contribue dp[i-1][j-1] en cas de correspondance (gratuitement), ou dp[i-1][j-1]+1 en cas de remplacement. Les deux algorithmes s’exécutent en temps O(mn).

def lcs_len(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
            else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
    return dp[m][n]

def edit_insert_delete_only(s1, s2):
    return len(s1) + len(s2) - 2 * lcs_len(s1, s2)

print(edit_insert_delete_only('sea', 'eat'))  # 2
print(edit_distance('sea', 'eat'))            # 2 (same here: replace not needed)

Appariement approximatif de chaînes

La distance d’édition est au cœur de l’appariement approximatif utilisé dans le monde réel. Un correcteur orthographique suggère des corrections situées à une ou deux modifications de distance du mot saisi. À grande échelle, le défi consiste à éviter O(mn × taille_du_dictionnaire) comparaisons. Les solutions comprennent les arbres BK (arbres métriques pour la distance d’édition), l’indexation par n-grammes et des algorithmes d’appariement approximatif de chaînes comme Bitap. Comprendre le DP sous-jacent vous aide à raisonner sur l’efficacité de ces outils de plus haut niveau.

def spell_suggest(typed, dictionary, max_dist=2):
    '''Return words in dictionary within max_dist edits of typed.'''
    suggestions = []
    for word in dictionary:
        if abs(len(typed) - len(word)) <= max_dist:
            if edit_distance(typed, word) <= max_dist:
                suggestions.append(word)
    return suggestions

def edit_distance(w1, w2):
    dp = list(range(len(w2)+1))
    for i,c1 in enumerate(w1,1):
        prev = i
        for j,c2 in enumerate(w2,1):
            temp = dp[j]
            dp[j] = prev if c1==c2 else 1+min(dp[j],prev,dp[j-1])
            prev = temp
    return dp[len(w2)]

dictionary = ['horse', 'worse', 'house', 'morse', 'nurse']
print(spell_suggest('harse', dictionary))  # horse, worse, house, morse

Distance d’édition pondérée

Dans certaines applications, les différentes opérations ont des coûts différents. Par exemple, transposer des caractères adjacents (une faute de frappe courante) peut coûter moins cher qu’un remplacement complet. La distance de Damerau-Levenshtein ajoute la transposition comme quatrième opération. Le DP est étendu ainsi : vérifiez également dp[i-2][j-2]+1 lorsque word1[i-1]==word2[j-2] et word1[i-2]==word2[j-1]. Cela modélise plus fidèlement les fautes de frappe au clavier.

def damerau_levenshtein(s, t):
    m, n = len(s), len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0]=i
    for j in range(n+1): dp[0][j]=j
    for i in range(1,m+1):
        for j in range(1,n+1):
            cost = 0 if s[i-1]==t[j-1] else 1
            dp[i][j] = min(
                dp[i-1][j]+1,     # delete
                dp[i][j-1]+1,     # insert
                dp[i-1][j-1]+cost # replace
            )
            # Transposition
            if i>1 and j>1 and s[i-1]==t[j-2] and s[i-2]==t[j-1]:
                dp[i][j] = min(dp[i][j], dp[i-2][j-2]+1)
    return dp[m][n]

print(damerau_levenshtein('CA', 'ABC'))   # 2
print(damerau_levenshtein('ab', 'ba'))    # 1 (transposition)

Alignement de séquences d’ADN

La bio-informatique utilise des variantes de la distance d’édition pour l’alignement de séquences d’ADN. L’algorithme de Needleman-Wunsch est un DP d’alignement global étroitement lié au LCS et à la distance d’édition : une correspondance rapporte +1, une non-correspondance rapporte -1 et un espace (insertion/suppression) entraîne une pénalité. La variante Smith-Waterman effectue un alignement local (elle trouve la sous-chaîne la plus similaire). Les deux sont des algorithmes DP en O(mn) qui utilisent la même structure de remplissage de table.

def needleman_wunsch(seq1, seq2, match=1, mismatch=-1, gap=-1):
    m, n = len(seq1), len(seq2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i * gap
    for j in range(n+1): dp[0][j] = j * gap
    for i in range(1,m+1):
        for j in range(1,n+1):
            score = match if seq1[i-1]==seq2[j-1] else mismatch
            dp[i][j] = max(
                dp[i-1][j-1] + score,  # align
                dp[i-1][j] + gap,      # gap in seq2
                dp[i][j-1] + gap       # gap in seq1
            )
    return dp[m][n]

print(needleman_wunsch('GATTACA', 'GCATGCU'))  # alignment score

Approche de la distance d’édition en entretien

Lorsqu’on vous demande de traiter la distance d’édition en entretien : (1) confirmez les opérations autorisées (insertion/suppression/remplacement) ; (2) définissez clairement l’état DP ; (3) écrivez explicitement les trois cas et la relation de récurrence ; (4) indiquez les cas de base : dp[i][0]=i et dp[0][j]=j ; (5) mentionnez l’optimisation de l’espace en O(n) ; (6) si le temps le permet, parcourez un petit exemple comme 'cat'→'cut' (1 remplacement) pour vérifier votre raisonnement. Le temps O(mn) et l’espace O(mn) → O(n) sont les bornes de complexité standard.

# Clean interview solution
def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    # O(n) space with rolling row
    dp = list(range(n + 1))
    for i in range(1, m + 1):
        diag = dp[0]   # dp[i-1][0]
        dp[0] = i
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i-1] == word2[j-1]:
                dp[j] = diag
            else:
                dp[j] = 1 + min(dp[j], dp[j-1], diag)
            diag = temp
    return dp[n]

# Time: O(mn), Space: O(n)
print(min_distance('horse', 'ros'))          # 3
print(min_distance('intention', 'execution')) # 5
print(min_distance('', 'abc'))               # 3
print(min_distance('abc', ''))               # 3

Vérification rapide

Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.

Récapitulatif de la leçon

Dans cette leçon, vous avez appris que : la distance d’édition suit la formule dp[i][j] = min(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+cost), avec cost=0 en cas de correspondance et 1 sinon, les cas de base dp[i][0]=i et dp[0][j]=j représentent la transformation vers une chaîne vide ou depuis celle-ci, et l’optimisation de l’espace en O(n) utilise un tableau 1D glissant avec une variable diagonale. Ensuite, nous appliquerons la même astuce du tableau glissant pour réduire l’espace des tables DP 2D de O(mn) à O(min(m,n)).

Questions Fréquemment Posées

La leçon « Distance d’édition (Levenshtein) » est-elle gratuite ?

Oui — le texte complet de « Distance d’édition (Levenshtein) » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Distance d’édition (Levenshtein) » ?

Déduisez la récurrence de la distance d’édition pour les opérations d’insertion, de suppression et de remplacement, puis remplissez le tableau de DP pour des paires de chaînes de longueurs variables. Tu pratiques Coding Interview Prep 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 Coding Interview Prep ?

Aucune expérience préalable n'est requise. Coding Interview Prep 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 3 sur 4.

Combien de temps prend la leçon « Distance d’édition (Levenshtein) » ?

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 Coding Interview Prep ?

Oui. Chaque leçon Coding Interview Prep 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

Chemins uniques et somme minimale des chemins sur des grilles
Plus longue sous-séquence commune
Distance d’édition (Levenshtein)
Optimisation de l’espace pour la DP 2D

← Retour à Coding Interview Prep