Längste gemeinsame Teilsequenz
Definieren Sie die LCS-Rekurrenz für zwei Strings, füllen Sie die 2D-Tabelle und rekonstruieren Sie die tatsächliche Teilsequenz durch Rückverfolgung in der Tabelle.
Längste gemeinsame Teilsequenz ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was ist eine Teilfolge?
Eine Teilfolge einer Zeichenkette entsteht, indem einige (oder keine) Zeichen gelöscht werden, ohne die Reihenfolge der verbleibenden Zeichen zu ändern. Beispielsweise ist „ACE“ eine Teilfolge von „ABCDE“, „AEC“ jedoch nicht (die Reihenfolge wurde verletzt). Die Longest Common Subsequence (LCS) zweier Zeichenketten ist die längste Teilfolge, die in beiden vorkommt. „ABCBDAB“ und „BDCABA“ haben die gemeinsame Teilfolge „BCBA“ oder „BDAB“ der Länge 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)) # TrueHerleitung der LCS-Rekurrenz
Definieren Sie dp[i][j] als die Länge der LCS von text1[:i] und text2[:j]. Wenn die Zeichen übereinstimmen (text1[i-1] == text2[j-1]), erweitern wir die LCS um 1: dp[i][j] = dp[i-1][j-1] + 1. Wenn sie nicht übereinstimmen, wählen wir die bessere Möglichkeit, indem wir ein Zeichen aus einer der beiden Zeichenketten überspringen: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Anfangsfall: dp[0][j] = dp[i][0] = 0 (die LCS mit einer leeren Zeichenkette hat die Länge 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')) # 2Die LCS-Tabelle nachvollziehen
Für text1='ABCD' und text2='ACBD': Beginnen Sie mit einer Tabelle voller Nullen. Wenn Zeichen übereinstimmen (A-A, C-C, B-B an der richtigen Position, D-D), gilt dp[i][j] = dp[i-1][j-1] + 1. Andernfalls nehmen Sie das Maximum der linken und oberen Nachbarn. Beim Durchlaufen der ausgefüllten Tabelle wird sichtbar, wie die diagonalen Schritte den übereinstimmenden Zeichen entsprechen. Der Endwert dp[4][4] gibt die Länge der LCS an.
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 der tatsächlichen LCS
Um die tatsächliche LCS-Zeichenkette zu ermitteln, verfolgen Sie die DP-Tabelle von dp[m][n] aus rückwärts. Wenn text1[i-1] == text2[j-1] gilt, gehört dieses Zeichen zur LCS – speichern Sie es und gehen Sie diagonal zu (i-1, j-1). Wenn dp[i-1][j] > dp[i][j-1] gilt, gehen Sie nach oben, andernfalls nach links. Kehren Sie die gesammelten Zeichen am Ende um, da Sie die Tabelle rückwärts durchlaufen haben. Diese Rekonstruktion benötigt O(m+n) Zeit.
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 BDABOptimierung des Speicherbedarfs auf O(n)
Die LCS-Tabelle benötigt nur die aktuelle und die vorherige Zeile. Sie können ein 1D-Array der Größe n+1 und eine Variable diagonal verwenden, um den Wert zu speichern, der zuvor bei dp[i-1][j-1] stand, bevor er überschrieben wurde. Durchlaufen Sie jede Zeile von links nach rechts. Nach jeder Zelle enthält das aktualisierte dp[j] den Wert der aktuellen Zeile, und Sie speichern den vorherigen Wert in diagonal, bevor Sie ihn überschreiben.
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')) # 4Zusammenhang zwischen LCS und Edit-Distanz
Die LCS ist eng mit der Edit-Distanz (Levenshtein-Distanz) verwandt. Wenn Sie die LCS kennen, können Sie die minimale Edit-Distanz nur mit Einfüge- und Löschoperationen berechnen: edit_dist = m + n - 2 * LCS(s1, s2). Jedes Zeichen aus s1, das nicht in der LCS vorkommt, erfordert eine Löschung, und jedes Zeichen aus s2, das nicht in der LCS vorkommt, erfordert eine Einfügung. Ersetzungen werden hier nicht gezählt, da wir nur Einfüge- und Löschoperationen erlauben. Die Formel ist jedoch für verwandte Probleme nützlich.
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')) # 5Löschoperation für zwei Zeichenketten
Löschoperation für zwei Zeichenketten (LeetCode 583) fragt nach der minimalen Anzahl von Löschungen, die erforderlich ist, um zwei Zeichenketten gleich zu machen. Zeichen, die Sie behalten, müssen eine gemeinsame Teilfolge bilden. Daher möchten Sie die LCS maximieren und alles andere löschen. Die Antwort lautet: m + n - 2 * LCS(s1, s2). Dies entspricht der oben beschriebenen Edit-Distanz mit Einfüge- und Löschoperationen. Probleme als LCS-Probleme zu formulieren, ist eine leistungsfähige Reduktionstechnik.
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 gemeinsame Teilzeichenkette
Verwechseln Sie die LCS (Teilfolge) nicht mit der längsten gemeinsamen Teilzeichenkette. Eine Teilzeichenkette ist zusammenhängend. Wenn Zeichen nicht übereinstimmen, wird der Zähler daher auf 0 zurückgesetzt, anstatt das Maximum der benachbarten Werte zu übernehmen. Die Rekurrenz ändert sich zu: Bei übereinstimmenden Zeichen gilt dp[i][j] = dp[i-1][j-1] + 1; andernfalls gilt dp[i][j] = 0. Verfolgen Sie den größten Wert, der in einer beliebigen Zelle auftritt.
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 für den Sequenzvergleich
Die LCS wird häufig in Diff-Tools wie Unix diff verwendet, um Dateien zu vergleichen. Die Änderungsfolge zwischen zwei Dateien wird aus der LCS abgeleitet: Zeilen in der LCS bleiben unverändert, zusätzliche Zeilen aus Datei 1 werden gelöscht und zusätzliche Zeilen aus Datei 2 werden eingefügt. Wenn Sie die LCS verstehen, können Sie besser nachvollziehen, wie Versionsverwaltungssysteme Änderungen nachverfolgen und warum Merge-Konflikte entstehen.
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)Kürzeste gemeinsame Supersequenz
Bei der kürzesten gemeinsamen Supersequenz (LeetCode 1092) wird die kürzeste Zeichenkette gesucht, die sowohl s1 als auch s2 als Teilfolgen enthält. Jedes Zeichen der LCS erscheint einmal in der Supersequenz; Nicht-LCS-Zeichen aus beiden Zeichenketten müssen ebenfalls enthalten sein. Länge = m + n - LCS(s1, s2). Zur Rekonstruktion verwenden Sie dasselbe Rückwärtsverfolgen wie bei der LCS, fügen jedoch an Positionen ohne Übereinstimmung Zeichen aus beiden Zeichenketten ein.
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-Komplexität und Tipps für Vorstellungsgespräche
Der klassische LCS-Algorithmus benötigt O(m×n) Zeit und O(m×n) Speicher und kann mit dem Trick des rollierenden Arrays auf O(min(m,n)) reduziert werden. Wichtige Tipps für Vorstellungsgespräche: (1) Definieren Sie vor dem Programmieren klar, was der DP-Zustand beschreibt. (2) Behandeln Sie die Fälle mit und ohne Übereinstimmung getrennt. (3) Wenn Sie nach der Rekonstruktion der Sequenz gefragt werden, erklären Sie zunächst das Rückwärtsverfolgen. (4) Erwähnen Sie die Longest Increasing Subsequence (LIS) als verwandtes 1D-Problem, das sich mit Patience-Sortierung in O(n log n) lösen lässt.
# 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)Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep, die in dieser Lektion behandelt werden.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Bei LCS gilt bei einer Übereinstimmung dp[i][j] = dp[i-1][j-1]+1, andernfalls max(dp[i-1][j], dp[i][j-1]), die tatsächliche Sequenz wird rekonstruiert, indem bei Übereinstimmungen diagonal und bei Nichtübereinstimmungen in Richtung des größeren Nachbarn zurückverfolgt wird, und die LCS die Grundlage für Edit-Distanz, Löschoperationen, kürzeste gemeinsame Supersequenzen und Diff-Tools bildet. Als Nächstes leiten Sie die Rekurrenz der Edit-Distanz (Levenshtein-Distanz) her, die den LCS-Ansatz um Ersetzungen erweitert.
Häufig gestellte Fragen
Ist die Lektion „Längste gemeinsame Teilsequenz“ kostenlos?
Ja — der vollständige Text von „Längste gemeinsame Teilsequenz“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Längste gemeinsame Teilsequenz“?
Definieren Sie die LCS-Rekurrenz für zwei Strings, füllen Sie die 2D-Tabelle und rekonstruieren Sie die tatsächliche Teilsequenz durch Rückverfolgung in der Tabelle. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Längste gemeinsame Teilsequenz“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Eindeutige Pfade und minimale Pfadsumme in Rastern
- Längste gemeinsame Teilsequenz
- Editierdistanz (Levenshtein)
- Speicheroptimierung für 2D-DP