Lengste felles delsekvens
Definer LCS-rekurrensen for to strenger, fyll 2D-tabellen og rekonstruer selve delsekvensen ved å gå bakover gjennom tabellen.
Lengste felles delsekvens er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva er en subsekvens?
En subsekvens av en streng dannes ved å slette noen eller ingen tegn uten å endre rekkefølgen på de gjenværende tegnene. «ACE» er for eksempel en subsekvens av «ABCDE», mens «AEC» ikke er det (rekkefølgen er brutt). Den lengste felles subsekvensen (LCS) av to strenger er den lengste subsekvensen som forekommer i begge. «ABCBDAB» og «BDCABA» har «BCBA» eller «BDAB» som felles LCS, begge med lengde 4.
# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)
# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')
print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern)) # TrueUtledning av LCS-rekurrensen
Definer dp[i][j] som lengden på LCS for text1[:i] og text2[:j]. Hvis tegnene er like (text1[i-1] == text2[j-1]), forlenges LCS-en med 1: dp[i][j] = dp[i-1][j-1] + 1. Hvis tegnene ikke er like, velges det beste alternativet ved å hoppe over ett tegn fra en av strengene: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Basistilfelle: dp[0][j] = dp[i][0] = 0 (LCS med en tom streng er 0).
def lcs_length(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # extend match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]
print(lcs_length('ABCBDAB', 'BDCABA')) # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC')) # 2Sporing gjennom LCS-tabellen
For text1='ABCD' og text2='ACBD': Start med bare nuller. Når tegnene samsvarer (A–A, C–C, B–B hvis de står på riktig plass, D–D), gjelder dp[i][j] = dp[i-1][j-1] + 1. Hvis de ikke samsvarer, velges maksimumet av naboene til venstre og over. Når man leser gjennom den utfylte tabellen, ser man hvordan de diagonale stegene tilsvarer samsvarende tegn. Den endelige verdien dp[4][4] gir LCS-lengden.
def lcs_trace(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Print table
print(' ', ' '.join(text2))
for i, row in enumerate(dp):
label = ' ' if i == 0 else text1[i-1]
print(label, row)
return dp[m][n]
lcs_trace('ABCD', 'ACBD')Gjenoppbygging av den faktiske LCS-en
For å hente frem den faktiske LCS-strengen må De gå bakover gjennom DP-tabellen fra dp[m][n]. Hvis text1[i-1] == text2[j-1], er dette tegnet med i LCS-en – noter det og gå diagonalt til (i-1, j-1). Hvis dp[i-1][j] > dp[i][j-1], går De oppover; ellers går De til venstre. Snu de innsamlede tegnene til slutt, siden tilbakesporingen gikk bakover. Denne gjenoppbyggingen bruker O(m+n) tid.
def lcs_reconstruct(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Backtrack
result = []
i, j = m, n
while i > 0 and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_reconstruct('ABCBDAB', 'BDCABA')) # BCBA or BDABPlassoptimalisering til O(n)
LCS-tabellen trenger bare gjeldende rad og forrige rad. Det kan brukes en 1D-array med størrelse n+1 og en variabel diagonal til å lagre verdien som lå i dp[i-1][j-1] før den ble overskrevet. Iterer fra venstre mot høyre for hver rad. Etter hver celle inneholder den oppdaterte dp[j] verdien for gjeldende rad, og den forrige verdien lagres i diagonal før overskriving.
def lcs_o1_space(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1) # represents previous row
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save current (will become diagonal for next j)
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_o1_space('ABCBDAB', 'BDCABA')) # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4Forholdet mellom LCS og redigeringsavstand
LCS er nært knyttet til redigeringsavstand (Levenshtein-avstand). Når LCS er kjent, kan den minste redigeringsavstanden beregnes ved å bruke bare innsettinger og slettinger: edit_dist = m + n - 2 * LCS(s1, s2). Hvert tegn som ikke er med i LCS-en fra s1, må slettes, og hvert tegn som ikke er med i LCS-en fra s2, må settes inn. Erstatning telles ikke med her, siden bare innsetting og sletting er tillatt, men formelen er nyttig i beslektede problemer.
def lcs_length(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 min_edits_insert_delete(s1, s2):
lcs = lcs_length(s1, s2)
return len(s1) + len(s2) - 2 * lcs
print(min_edits_insert_delete('ABCD', 'ANCD')) # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros')) # 5Sletteoperasjon for to strenger
Sletteoperasjon for to strenger (LeetCode 583) spør etter det minste antallet slettinger som trengs for å gjøre to strenger like. Tegnene som beholdes, må utgjøre en felles delsekvens, så målet er å maksimere LCS-en og slette alt annet. Svar: m + n - 2 * LCS(s1, s2). Dette er ekvivalent med redigeringsavstanden med innsetting og sletting ovenfor. Å formulere problemer ved hjelp av LCS er en kraftig reduksjonsteknikk.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
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] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs = dp[m][n]
return m + n - 2 * lcs # deletions needed
print(min_distance('sea', 'eat')) # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco')) # 4Lengste felles delstreng
Ikke forveksle LCS (delsekvens) med lengste felles delstreng. En delstreng er sammenhengende, så hvis tegnene ikke samsvarer, tilbakestilles antallet til 0 i stedet for å ta maksverdien av naboene. Rekurrensen endres til: hvis tegnene samsvarer, dp[i][j] = dp[i-1][j-1] + 1; ellers dp[i][j] = 0. Hold oversikt over den største verdien blant alle cellene.
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
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
max_len = max(max_len, dp[i][j])
# else dp[i][j] stays 0 (reset)
return max_len
# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA')) # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA')) # 2 (BD or AB)LCS for sekvenssammenligning
LCS brukes mye i diff-verktøy (for eksempel Unix diff) til å sammenligne filer. Redigeringsskriptet mellom to filer utledes fra LCS-en: linjer i LCS-en er uendret, ekstra linjer fra fil 1 slettes, og ekstra linjer fra fil 2 settes inn. Forståelse av LCS gjør det lettere å se hvordan versjonskontrollsystemer sporer endringer, og hvorfor sammenslåingskonflikter oppstår.
def diff(old_lines, new_lines):
'''Simple diff using LCS to find unchanged lines.'''
m, n = len(old_lines), len(new_lines)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Backtrack to produce diff
output, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
output.append(' '+old_lines[i-1]); i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
output.append('+ '+new_lines[j-1]); j-=1
else:
output.append('- '+old_lines[i-1]); i-=1
return list(reversed(output))
for line in diff(['a','b','c'], ['a','x','c']): print(line)Korteste felles supersekvens
Korteste felles supersekvens (LeetCode 1092) spør etter den korteste strengen som har både s1 og s2 som delsekvenser. Hvert tegn i LCS-en forekommer én gang i supersekvensen, mens tegn som ikke er med i LCS-en, fra begge strengene må inkluderes. Lengde = m + n - LCS(s1, s2). For å gjenoppbygge den brukes samme tilbakesporing som for LCS, men tegn fra begge strengene inkluderes ved posisjoner som ikke samsvarer.
def shortest_common_supersequence(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])
# Reconstruct
result, i, j = [], m, n
while i>0 and j>0:
if s1[i-1]==s2[j-1]: result.append(s1[i-1]); i-=1; j-=1
elif dp[i-1][j]>dp[i][j-1]: result.append(s1[i-1]); i-=1
else: result.append(s2[j-1]); j-=1
while i>0: result.append(s1[i-1]); i-=1
while j>0: result.append(s2[j-1]); j-=1
return ''.join(reversed(result))
print(shortest_common_supersequence('abac', 'cab')) # 'cabac' length 5LCS-kompleksitet og tips til jobbintervju
Den klassiske LCS-algoritmen bruker O(m×n) tid og O(m×n) plass, og kan reduseres til O(min(m,n)) plass med trikset med et rullende array. Viktige tips til jobbintervju: (1) Definer tydelig hva DP-tilstanden representerer før kodingen starter. (2) Behandle tilfellene med treff og uten treff separat. (3) Når De blir bedt om å gjenoppbygge sekvensen, bør De beskrive tilbakesporingen før De koder den. (4) Nevn Longest Increasing Subsequence (LIS) som et beslektet 1D-problem som kan løses på O(n log n) med patience sorting.
# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left
def lis_length(nums):
'''Patience sorting: O(n log n) LIS length.'''
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,101 or 2,5,7,18)Rask sjekk
Test forståelsen Deres av Data Structures & Algorithms — Coding Interview Prep-konseptene fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De: LCS bruker dp[i][j] = dp[i-1][j-1]+1 ved treff, ellers max(dp[i-1][j], dp[i][j-1]), den faktiske sekvensen gjenoppbygges ved å gå diagonalt bakover ved treff og mot den største naboen ved avvik, og LCS danner grunnlaget for redigeringsavstand, sletteoperasjoner, korteste felles supersekvens og diff-verktøy. Neste steg er å utlede rekurrensen for redigeringsavstand (Levenshtein), som legger til erstatninger i LCS-rammeverket.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Lengste felles delsekvens» gratis?
Ja – hele teksten i «Lengste felles delsekvens» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Lengste felles delsekvens»?
Definer LCS-rekurrensen for to strenger, fyll 2D-tabellen og rekonstruer selve delsekvensen ved å gå bakover gjennom tabellen. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.
Hvor lang tid tar leksjonen «Lengste felles delsekvens»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Unike stier og minste stisum i rutenett
- Lengste felles delsekvens
- Edit distance (Levenshtein)
- Plassoptimalisering for 2D-DP