Edit Distance

Q: Come si ottiene l’elenco delle modifiche, non solo il conteggio?

Mantieni l'intera tabella e procedi a ritroso da dp[n][m] . Se le lettere coincidono, spostati in diagonale senza modifiche. Altrimenti, spostati verso la cella adiacente il cui valore è inferiore di uno: la diagonale corrisponde a una sostituzione, verso l'alto a un'eliminazione, verso sinistra a un inserimento. Fermati a dp[0][0] e leggi le modifiche al contrario. La versione a due righe non può farlo da sola, perché ha eliminato le righe precedenti.

Q: È possibile risolvere la distanza di modifica con un unico array?

Sì. Riempi un array row sul posto, da sinistra a destra. Prima di sovrascrivere row[j] , contiene ancora il valore della riga precedente, mentre row[j-1] contiene già quello della riga corrente. L’unico valore che perdi è quello della diagonale, quindi conservalo in una variabile: salva il vecchio row[j] prima di scrivere e usalo come diagonale per j + 1 .

DifficileProgrammazione dinamica

+10

Ti vengono date due parole, word1 e word2. Una modifica cambia word1 in uno di tre modi: inserire una lettera in qualsiasi posizione, eliminare una lettera o sostituire una lettera con un’altra. Restituisci il numero minimo di modifiche necessarie per trasformare word1 in word2.

Funzione

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

word1string: la parola che modifichi
word2string: la parola da raggiungere
Restituisceinteger: il minor numero di inserimenti, eliminazioni e sostituzioni che trasformano word1 in word2

Vincoli

1 ≤ word1.length ≤ 500
1 ≤ word2.length ≤ 500
Entrambe le parole contengono solo lettere minuscole dell’alfabeto inglese.

Esempi

Input: word1 = "spot"word2 = "stop"
Output: 2
Spiegazione: Sostituisci la p con la t e la t con la p: spot diventa stot, poi stop. Una modifica non è sufficiente, perché le parole differiscono in due punti e un inserimento o un’eliminazione ne cambierebbe la lunghezza.

Input: word1 = "garden"word2 = "ardent"
Output: 2
Spiegazione: Elimina la g per ottenere arden, poi inserisci t alla fine per ottenere ardent. Sostituire una lettera alla volta costerebbe 6, perché le due parole differiscono in ogni posizione.

Input: word1 = "rain"word2 = "shine"
Output: 3
Spiegazione: Sostituisci r con s e a con h per ottenere shin, poi inserisci e. Non bastano due modifiche: r e a non compaiono in shine, quindi ognuna richiede una modifica che non allunga la parola, e la parola deve comunque allungarsi di una lettera.

+21 test nascosti all’invio

Per approfondire

Puoi anche restituire l'elenco più breve delle modifiche, non solo indicare quante sono?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Le modifiche interagiscono, quindi non puoi correggere le parole posizione per posizione: garden e ardent differiscono in tutte e sei le posizioni, eppure bastano due modifiche quando si elimina la g e tutto si sposta a sinistra. L'idea risolutiva è considerare solo l'ultima lettera di ciascuna parola. O le due lettere sono già uguali, oppure una delle sole tre modifiche possibili le rende uguali, e ogni scelta lascia lo stesso problema su prefissi più corti. Una tabella di risposte (n+1) × (m+1) risolve una volta sola ogni coppia di prefissi, e bastano due righe della tabella.

Prova tutte e tre le modifiche con la ricorsione

Corretto, ma non termina sui test più grandi

Intuizione

Sia edits(i, j) il numero minimo di modifiche necessarie per trasformare il suffisso word1[i:] in word2[j:]. Guarda le prime lettere dei due suffissi. Se sono uguali, conservale e fai avanzare entrambi gli indici: una lettera corrispondente non richiede mai una modifica, e qualsiasi piano che spende una modifica per essa può essere trasformato in uno che la conserva senza diventare più lungo.

Se sono diverse, una modifica deve intervenire su word1[i] o produrre word2[j], e ci sono esattamente tre possibilità. Sostituisci word1[i] con word2[j] e fai avanzare entrambi gli indici: edits(i+1, j+1). Elimina word1[i] e fai avanzare solo i: edits(i+1, j). Inserisci word2[j] davanti a essa e fai avanzare solo j: edits(i, j+1). La risposta è 1 più il costo minimo delle tre possibilità. Quando word1 termina, inserisci il resto di word2, con un costo di m - j; quando word2 termina, elimina il resto di word1, con un costo di n - i.

È lento perché ogni mancata corrispondenza avvia tre chiamate. Per due parole di 15 lettere senza lettere in comune, si arriva a circa 6.7 × 10^10 chiamate, e i test più impegnativi hanno 500 lettere ciascuno. Eppure ci sono solo (n+1) × (m+1) coppie (i, j) diverse, quindi quasi ogni chiamata ripete una chiamata già effettuata.

Algoritmo

Scrivi edits(i, j) per i suffissi che iniziano in i e j.
Se i supera la fine di word1, restituisci m - j; se j supera la fine di word2, restituisci n - i.
Se word1[i] == word2[j], restituisci edits(i+1, j+1).
Altrimenti restituisci 1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1)) per sostituire, eliminare e inserire.
La risposta è 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)

Completa una tabella di prefissi

Intuizione

Stato. Sia dp[i][j] il numero minimo di modifiche necessarie per trasformare le prime i lettere di word1 nelle prime j lettere di word2. L’indice 0 indica un prefisso vuoto.

Transizioni. Confronta le ultime lettere dei due prefissi, word1[i-1] e word2[j-1]. Se sono uguali, mantienile: dp[i][j] = dp[i-1][j-1], la cella in diagonale in alto a sinistra. Se non lo sono, aggiungi una modifica e scegli il minimo tra tre celle vicine. La diagonale dp[i-1][j-1] indica di sostituire word1[i-1] con word2[j-1]. La cella sopra, dp[i-1][j], indica di eliminare word1[i-1]. La cella a sinistra, dp[i][j-1], indica di inserire word2[j-1] alla fine.

Riga e colonna di base. A differenza di molti problemi sulle tabelle, non contengono zeri. Per trasformare i lettere in un prefisso vuoto servono i eliminazioni, quindi dp[i][0] = i. Per costruire j lettere dal nulla servono j inserimenti, quindi dp[0][j] = j. Ogni cella legge la cella sopra, quella a sinistra e quella in diagonale, quindi riempiendo la tabella riga per riga, da sinistra a destra, queste celle sono già pronte. La risposta è dp[n][m].

Ecco la tabella per trasformare spot in stop, con le colonne corrispondenti ai prefissi "", s, st, sto, stop. La riga "" è [0, 1, 2, 3, 4], la riga s è [1, 0, 1, 2, 3], la riga sp è [2, 1, 1, 2, 2], la riga spo è [3, 2, 2, 1, 2] e la riga spot è [4, 3, 2, 2, 2]. Esaminiamo alcune celle. s e s corrispondono, quindi si copia il valore diagonale 0. sp e st non corrispondono: le celle vicine contengono 0 in diagonale, 1 sopra e 1 a sinistra, quindi il valore è 1 + 0 = 1, una sostituzione. spo e sto corrispondono sulla o, quindi si copia il valore diagonale 1. L’ultima cella, spot e stop, confronta t con p: le celle vicine contengono 1, 2 e 2, quindi la risposta è 1 + 1 = 2.

La tabella ha (n+1) × (m+1) celle, ognuna con un numero costante di operazioni: circa 2.5 × 10^5 passaggi per due parole di 500 lettere. Una ricorsione con memoizzazione riempie le stesse celle, ma può raggiungere una profondità di n + m chiamate ricorsive, superando il limite predefinito di Python, pari a 1000.

Algoritmo

Crea una tabella dp di (n+1) × (m+1) celle.
Imposta dp[i][0] = i per ogni i e dp[0][j] = j per ogni j.
Per i da 1 a n e j da 1 a m, se word1[i-1] == word2[j-1], imposta dp[i][j] = dp[i-1][j-1].
Altrimenti imposta dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).
Restituisci 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]

Mantieni solo due righe

Intuizione

La riga i legge solo la riga i-1 e le proprie celle a sinistra. Una volta completata una riga, le righe precedenti non vengono più lette. Mantieni due array: prev per la riga completata e cur per la riga che stai compilando, e scambiali dopo ogni riga. Le transizioni non cambiano: la diagonale è prev[j-1], sopra è prev[j] e a sinistra è cur[j-1].

La colonna di base non scompare. Ora si trova nella prima voce di ogni riga, quindi imposta cur[0] = i prima di compilare la riga i. La riga 0 inizia come [0, 1, 2, ..., m], la riga di base.

Trasformare word2 in word1 richiede lo stesso numero di modifiche, perché ogni inserimento diventa un'eliminazione e ogni eliminazione un inserimento. Quindi puoi scambiare le parole e far scorrere le righe lungo quella più corta. Ogni riga conterrà così min(n, m) + 1 numeri invece di una tabella con un massimo di 251,001 celle, e il lavoro rimane O(n × m).

Algoritmo

Se word2 è più lungo di word1, scambiali.
Imposta prev = [0, 1, ..., m], dove m è la lunghezza minore.
Per ogni i da 1 a n, imposta cur[0] = i, poi riempi cur[1..m] con la stessa regola, leggendo la diagonale e la cella sopra da prev e quella a sinistra da cur.
Scambia prev e cur.
Restituisci 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]

Trappole e casi limite

La ricorrenza è breve, quindi la maggior parte degli errori si trova nei casi base o nel vicino che viene letto.

Riempire di zeri la riga 0 e la colonna 0, come nella sottosequenza comune più lunga. Trasformare abc in un prefisso vuoto costa 3 eliminazioni, non 0, quindi dp[i][0] deve essere i e dp[0][j] deve essere j.
Dimenticare cur[0] = i nella versione a due righe. Il primo elemento conserva un valore di due righe prima e ogni cella successiva è errata.
Pagare una modifica in caso di corrispondenza. dp[i][j] = 1 + min(...) per lettere uguali fa sì che trasformare a in a costi 1. In caso di corrispondenza, copia la diagonale.
Leggere il vicino a sinistra da prev invece che da cur. Sinistra è la riga corrente: è l’inserimento di word2[j-1] dopo che word1[:i] è già stata trasformata in word2[:j-1].
Confrontare posizione per posizione. Contare le posizioni in cui le parole differiscono ignora inserimenti ed eliminazioni: dà 6 per garden e ardent, mentre la risposta è 2.
Usare la memoizzazione con la ricorsione su parole di 500 lettere. La profondità delle chiamate raggiunge 1000, che è il limite predefinito di Python.

Domande frequenti4

Qual è la complessità temporale della distanza di modifica?

La soluzione con la tabella ha una complessità temporale di O(n × m), dove n e m sono le due lunghezze, perché riempie una cella per ogni coppia di prefissi con un lavoro costante. Usa O(n × m) di memoria per la tabella completa, oppure O(min(n, m)) con due righe. La ricorsione semplice senza tabella ha una complessità esponenziale.

La distanza di modifica è la stessa cosa della distanza di Levenshtein?

Sì, questa versione è la distanza di Levenshtein: inserire, eliminare e sostituire hanno ciascuno un costo unitario. Distanza di modifica è il nome della famiglia. Altre varianti consentono meno o più modifiche: solo inserimenti ed eliminazioni danno n + m - 2 × LCS, solo sostituzioni su stringhe della stessa lunghezza danno la distanza di Hamming, mentre aggiungere lo scambio di due lettere adiacenti dà la variante di Damerau.

Come si ottiene l’elenco delle modifiche, non solo il conteggio?

Mantieni l'intera tabella e procedi a ritroso da dp[n][m]. Se le lettere coincidono, spostati in diagonale senza modifiche. Altrimenti, spostati verso la cella adiacente il cui valore è inferiore di uno: la diagonale corrisponde a una sostituzione, verso l'alto a un'eliminazione, verso sinistra a un inserimento. Fermati a dp[0][0] e leggi le modifiche al contrario. La versione a due righe non può farlo da sola, perché ha eliminato le righe precedenti.

È possibile risolvere la distanza di modifica con un unico array?

Sì. Riempi un array row sul posto, da sinistra a destra. Prima di sovrascrivere row[j], contiene ancora il valore della riga precedente, mentre row[j-1] contiene già quello della riga corrente. L’unico valore che perdi è quello della diagonale, quindi conservalo in una variabile: salva il vecchio row[j] prima di scrivere e usalo come diagonale per j + 1.

Python

def minDistance(word1, word2):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

word1 = "spot"
word2 = "stop"

Atteso

Edit Distance

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova tutte e tre le modifiche con la ricorsione

Completa una tabella di prefissi

Mantieni solo due righe

Trappole e casi limite

Domande frequenti4

Problemi simili