Distanza di edit passo dopo passo
Inserire, eliminare e sostituire per trasformare una stringa
Distanza di edit passo dopo passo è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Che cosa misura la distanza di modifica
La distanza di modifica è il numero minimo di modifiche di un singolo carattere necessarie per trasformare una stringa in un'altra. Misura quanto due parole siano realmente diverse.
Le tre operazioni
Per ogni modifica si può inserire, eliminare o sostituire un carattere. Nel problema standard, ogni operazione ha esattamente costo uno.
Definire lo stato
Indichiamo con dp[i][j] il numero di modifiche necessarie per trasformare i primi i caratteri di A nei primi j caratteri di B.
Coincidenza gratuita
Se i caratteri correnti coincidono già, non serve alcuna modifica. È sufficiente riportare direttamente il valore della diagonale.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1]Altrimenti, si paga uno
Quando i caratteri sono diversi, si sceglie il vicino meno costoso e si aggiunge una modifica. Questo min più uno copre tutte e tre le operazioni.
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])Quale vicino rappresenta cosa
La cella sopra rappresenta una eliminazione, quella a sinistra un inserimento e quella in diagonale una sostituzione. Il min sceglie semplicemente l'opzione meno costosa.
I casi base delle stringhe vuote
Per trasformare una stringa di lunghezza i in una stringa vuota servono i eliminazioni. Si riempiono quindi la prima riga e colonna con 0, 1, 2 e così via.
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = jDimensionare la tabella
Utilizzi una griglia n+1 per m+1, così i prefissi vuoti hanno una propria riga e colonna. Questo riempimento mantiene semplici i cicli.
dp = [[0] * (m+1) for _ in range(n+1)]Riempire secondo l'ordine corretto
Scorra i valori di i e j partendo da 1. Ogni cella dipende soltanto dai vicini sopra, a sinistra e in diagonale, già riempiti.
for i in range(1, n+1):
for j in range(1, m+1):
...Leggere la distanza
Il numero minimo di modifiche finisce nell'angolo. La risposta è dp[n][m] quando la tabella è completa.
distance = dp[n][m]Costi e varianti
Questo algoritmo richiede tempo O(n per m). Nei problemi reali, le diverse operazioni possono avere costi differenti, ma la stessa ricorrenza continua a funzionare.
Verifica rapida
I caratteri A[i-1] e B[j-1] sono diversi. Quale ricorrenza calcola la distanza di modifica?
Riepilogo: distanza di modifica
Una coincidenza significa riportare la diagonale; una differenza significa 1 più il min dei tre vicini. Inizializzi i bordi e legga dp[n][m]. ✏️
Impara Python con un tutor IA — gratis
Scrivi ed esegui vero codice nel tuo browser, ricevi aiuto istantaneo da un tutor IA disponibile 24/7, e riprendi da dove hai lasciato sul web o nell'app.
- Corsi
- 30
- Lezioni
- 120
Domande Frequenti
La lezione «Distanza di edit passo dopo passo» è gratuita?
Sì — il testo completo di «Distanza di edit passo dopo passo» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Distanza di edit passo dopo passo»?
Inserire, eliminare e sostituire per trasformare una stringa Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Distanza di edit passo dopo passo»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Contare i cammini su una griglia
- Somma minima dei cammini con ostacoli
- Sottosequenza comune più lunga
- Distanza di edit passo dopo passo