Sottosequenza comune più lunga
Allineare due stringhe con una tabella DP
Sottosequenza comune più lunga è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Che cos'è una sottosequenza
Una sottosequenza mantiene i caratteri nello stesso ordine, ma può saltarne alcuni. Da 'abcde' si può ottenere 'ace', ma mai 'aec'.
L'obiettivo della LCS
Date due stringhe, la sottosequenza comune più lunga è la sequenza più lunga che compare in entrambe mantenendo lo stesso ordine relativo.
Passare a una griglia
Si confrontano i prefissi delle due stringhe. Una tabella bidimensionale basata sulle loro lunghezze trasforma il problema in una familiare DP su griglia.
Definire lo stato
Indichiamo con dp[i][j] la lunghezza della LCS dei primi i caratteri di A e dei primi j caratteri di B.
Quando i caratteri coincidono
Se A[i-1] è uguale a B[j-1], quella lettera condivisa estende la LCS. Si aggiunge uno al valore della diagonale dp[i-1][j-1].
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1Quando sono diversi
Se le lettere sono diverse, si elimina un carattere da una delle due stringhe e si conserva il risultato migliore. Si prende il max dei due vicini.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])Il caso base
Un prefisso vuoto non condivide alcun carattere, quindi la lunghezza della LCS è zero. La riga 0 e la colonna 0 restano composte interamente da zeri.
dp = [[0] * (m+1) for _ in range(n+1)]Una riga e una colonna in più
Dimensionare la tabella come n+1 per m+1 fornisce un bordo di zeri gratuito. In questo modo si eliminano gli scomodi controlli dei limiti ai bordi.
Riempirla
Si scorrano i valori di i e j partendo da 1. Ogni cella ha bisogno soltanto dei valori sopra, a sinistra e in diagonale, che sono già stati calcolati.
for i in range(1, n+1):
for j in range(1, m+1):
...Leggere la lunghezza
La lunghezza completa della LCS si trova nell'angolo. La risposta è dp[n][m] dopo aver riempito tutte le celle.
length = dp[n][m]Complessità
Si visita ogni cella una sola volta, quindi il lavoro richiede tempo e memoria O(n per m). Questo gestisce senza problemi stringhe lunghe fino a qualche migliaio di caratteri.
Verifica rapida
I caratteri correnti A[i-1] e B[j-1] sono uguali. Quale aggiornamento è corretto?
Riepilogo: LCS
Costruisca una tabella n+1 per m+1: in caso di coincidenza aggiunga uno alla diagonale, altrimenti prenda il vicino con valore max. L'angolo contiene la lunghezza. 🔗
Domande Frequenti
La lezione «Sottosequenza comune più lunga» è gratuita?
Sì — il testo completo di «Sottosequenza comune più lunga» è 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Sottosequenza comune più lunga»?
Allineare due stringhe con una tabella DP Eserciti Coding Interview Prep 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Sottosequenza comune più lunga»?
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 Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep 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