Længste fælles delsekvens
Justér to strenge med en DP-tabel
Længste fælles delsekvens er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad en delsekvens er
En delsekvens bevarer tegnene i deres rækkefølge, men kan springe nogle over. Fra 'abcde' kan du tage 'ace', men aldrig 'aec'.
Målet med LCS
Givet to strenge er den længste fælles delsekvens den længste sekvens, der optræder i begge strenge i den samme indbyrdes rækkefølge.
Gå over til et gitter
Sammenlign præfikser af de to strenge. En 2D-tabel over deres længder gør dette til velkendt gitter-DP.
Definér tilstanden
Lad dp[i][j] være LCS-længden for de første i tegn af A og de første j tegn af B.
Når tegnene er ens
Hvis A[i-1] er lig med B[j-1], udvider det fælles bogstav LCS. Du lægger én til værdien på diagonalen, dp[i-1][j-1].
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1Når de er forskellige
Hvis tegnene er forskellige, fjerner du ét tegn fra en af strengene og beholder det bedste resultat. Du tager max af de to naboer.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])Basistilfældet
Et tomt præfiks har ingen fælles tegn, så LCS-længden er nul. Række 0 og kolonne 0 forbliver fyldt med nuller.
dp = [[0] * (m+1) for _ in range(n+1)]Én ekstra række og kolonne
Hvis du dimensionerer tabellen til n+1 gange m+1, får du en gratis nul-kant. Det fjerner besværlige grænsekontroller ved kanterne.
Udfyld den
Gå gennem i og j fra 1 og opefter. Hver celle har kun brug for værdierne ovenfor, til venstre og på diagonalen, som allerede er beregnet.
for i in range(1, n+1):
for j in range(1, m+1):
...Læs længden
Den fulde LCS-længde ligger i hjørnet. Svaret er dp[n][m], når alle celler er udfyldt.
length = dp[n][m]Kompleksitet
Du besøger hver celle én gang, så arbejdet kræver O(n gange m) tid og hukommelse. Det håndterer uden problemer strenge på op til nogle få tusinde tegn.
Hurtigt tjek
De aktuelle tegn A[i-1] og B[j-1] er ens. Hvilken opdatering er korrekt?
Opsummering: LCS
Byg en tabel på n+1 gange m+1: læg én til diagonalen, når tegnene er ens, og vælg ellers den største nabo. Hjørnet indeholder længden. 🔗
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Længste fælles delsekvens” gratis?
Ja — hele teksten til “Længste fælles delsekvens” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Længste fælles delsekvens”?
Justér to strenge med en DP-tabel Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Længste fælles delsekvens”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Stitælling i et gitter
- Mindste stisum med forhindringer
- Længste fælles delsekvens
- Edit distance trin for trin