Overview
Längste gemeinsame Teilsequenz: die längste Zeichenfolge, die in beiden Strings in Reihenfolge erscheint.
Analogy
Zwei DNA-Stränge mit gemeinsamem genetischem Signal: den längsten gemeinsamen Faden finden.
Step-by-step
- dp[i][j] = LCS-Länge von s1[:i] und s2[:j].
- Wenn s1[i-1]==s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1.
- Sonst: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
- Antwort ist dp[m][n].
Visual
s1='ABCBD', s2='ACBD': dp-Tabelle → LCS=3 ('ABD')
Common mistakes
- LCS (Teilsequenz, nicht zusammenhängend) mit längstem gemeinsamen Teilstring (zusammenhängend) verwechseln.
- (m+1)×(n+1) Tabelle allokieren aber ab Index 0 falsch indizieren.
Practice questions
- Eigentlichen LCS-String durch Rückverfolgung rekonstruieren.
- Edit-Distanz berechnen (ED = m+n-2*LCS).
Space
O(m×n), O(min(m,n)) mit Rolling Rows