Længste fælles delsekvens
Definer LCS-rekurrensen for to strenge, udfyld 2D-tabellen, og genskab den faktiske delsekvens ved at gå baglæns gennem tabellen.
Længste fælles delsekvens er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 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 er en delsekvens?
En delsekvens af en streng dannes ved at slette nogle (eller ingen) tegn uden at ændre rækkefølgen af de resterende tegn. For eksempel er 'ACE' en delsekvens af 'ABCDE', men 'AEC' er ikke (rækkefølgen er forkert). Den længste fælles delsekvens (LCS) af to strenge er den længste delsekvens, der forekommer i begge. 'ABCBDAB' og 'BDCABA' har den fælles delsekvens 'BCBA' eller 'BDAB' med længden 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)) # TrueUdledning af LCS-rekursionen
Definér dp[i][j] som længden af LCS for text1[:i] og text2[:j]. Hvis tegnene matcher (text1[i-1] == text2[j-1]), udvider vi LCS med 1: dp[i][j] = dp[i-1][j-1] + 1. Hvis de ikke matcher, vælger vi det bedste resultat ved at springe et tegn over fra en af strengene: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Basistilfælde: dp[0][j] = dp[i][0] = 0 (LCS for 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 gennem LCS-tabellen
For text1='ABCD' og text2='ACBD': Start med lutter nuller. Når tegn matcher (A-A, C-C, B-B hvis de står på den rigtige plads, D-D), gælder dp[i][j] = dp[i-1][j-1] + 1. Ellers tager du maksimum af naboerne til venstre og ovenfor. Når du gennemgår den udfyldte tabel, kan du se, hvordan de diagonale trin svarer til matchende tegn. Den endelige værdi dp[4][4] giver LCS-længden.
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')Rekonstruktion af den faktiske LCS
For at genskabe den faktiske LCS-streng skal du gå baglæns gennem DP-tabellen fra dp[m][n]. Hvis text1[i-1] == text2[j-1], er dette tegn en del af LCS'en — registrér det, og gå diagonalt til (i-1, j-1). Hvis dp[i-1][j] > dp[i][j-1], skal du gå opad; ellers til venstre. Vend de indsamlede tegn om til sidst, fordi du gik baglæns. Denne rekonstruktion har en tidskompleksitet på O(m+n).
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 BDABPladsoptimering til O(n)
LCS-tabellen behøver kun den aktuelle række og den forrige række. Du kan bruge et 1D-array med størrelsen n+1 og en variabel diagonal til at gemme den værdi, der stod i dp[i-1][j-1], før den blev overskrevet. Gå fra venstre mod højre for hver række. Efter hver celle indeholder den opdaterede dp[j] værdien for den aktuelle række, og du gemmer den forrige værdi i diagonal, før den overskrives.
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 mellem LCS og redigeringsafstand
LCS er tæt forbundet med redigeringsafstand (Levenshtein-afstand). Hvis du kender LCS'en, kan du beregne den minimale redigeringsafstand udelukkende ved hjælp af indsættelser og sletninger: edit_dist = m + n - 2 * LCS(s1, s2). Hvert tegn fra s1, der ikke er i LCS'en, kræver en sletning, og hvert tegn, der ikke er i LCS'en fra s2, kræver en indsættelse. Erstatning tælles ikke med her, da vi kun tillader indsættelse og sletning, men denne formel er nyttig i relaterede 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')) # 5Sletteoperation for to strenge
Sletteoperation for to strenge (LeetCode 583) spørger efter det mindste antal sletninger, der skal til for at gøre to strenge ens. Tegn, du beholder, skal udgøre en fælles delsekvens, så du skal maksimere LCS'en og slette alt andet. Svar: m + n - 2 * LCS(s1, s2). Dette svarer til redigeringsafstanden med indsættelser og sletninger ovenfor. At formulere problemer med LCS er en effektiv reduktionsteknik.
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')) # 4Længste fælles delstreng
Forveksl ikke LCS (delsekvens) med længste fælles delstreng. En delstreng er sammenhængende, så hvis tegnene ikke matcher, nulstilles tællingen til 0 i stedet for at tage maksimum af naboerne. Rekurrensen ændres til: hvis tegnene matcher dp[i][j] = dp[i-1][j-1] + 1; ellers dp[i][j] = 0. Hold styr på den største værdi, der er set, på tværs af alle celler.
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 til sammenligning af sekvenser
LCS bruges i vid udstrækning i diff-værktøjer (som Unix diff) til at sammenligne filer. Ændringssekvensen mellem to filer udledes af LCS'en: linjer i LCS'en er uændrede, ekstra linjer fra fil 1 slettes, og ekstra linjer fra fil 2 indsættes. Når du forstår LCS, bliver det lettere at se, hvordan versionsstyringssystemer registrerer ændringer, og hvorfor flettekonflikter opstå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 fælles supersekvens
Den korteste fælles supersekvens (LeetCode 1092) er den korteste streng, der har både s1 og s2 som delsekvenser. Alle tegn fra LCS'en forekommer én gang i supersekvensen; tegn, der ikke er i LCS'en, fra begge strenge skal medtages. Længde = m + n - LCS(s1, s2). Sådan rekonstruerer du den: brug samme LCS-tilbagevandring, men medtag tegn fra begge strenge ved positioner, der ikke matcher.
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 jobsamtalen
Den klassiske LCS-algoritme har tidsforbruget O(m×n) og pladsforbruget O(m×n), som kan reduceres til O(min(m,n)) med tricket med en rullende array. Vigtige tips til jobsamtalen: (1) Definér tydeligt, hvad DP-tilstanden repræsenterer, før du koder. (2) Håndtér match- og intet-match-tilfældene særskilt. (3) Når du bliver bedt om at rekonstruere sekvensen, skal du beskrive tilbagevandringen, før du koder den. (4) Nævn Længste stigende delsekvens (LIS) som et beslægtet 1D-problem, der kan løses i 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)Hurtigt tjek
Test din forståelse af begreberne fra lektionen i Data Structures & Algorithms — Coding Interview Prep.
Opsummering af lektionen
I denne lektion lærte du: LCS bruger dp[i][j] = dp[i-1][j-1]+1 ved match, ellers max(dp[i-1][j], dp[i][j-1]), den faktiske sekvens rekonstrueres ved at gå diagonalt baglæns ved match og mod den største nabo ved uoverensstemmelser, og LCS ligger til grund for redigeringsafstand, sletteoperationer, korteste fælles supersekvens og diff-værktøjer. Som det næste udleder vi rekurrensen for redigeringsafstand (Levenshtein), som føjer erstatninger til LCS-rammen.
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”?
Definer LCS-rekurrensen for to strenge, udfyld 2D-tabellen, og genskab den faktiske delsekvens ved at gå baglæns gennem tabellen. 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 2 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
- Unikke stier og minimal stisum i grids
- Længste fælles delsekvens
- Edit distance (Levenshtein)
- Pladsoptimering for 2D-DP