Längste palindromische Teilfolge und Teilzeichenkette
Wenden Sie Intervall-DP an, um die längste palindromische Teilfolge zu finden, und nutzen Sie den Trick des Ausdehnens um die Mitte für die längste palindromische Teilzeichenkette.
Längste palindromische Teilfolge und Teilzeichenkette ist eine kostenlose Coding 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 Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Palindromdefinitionen erneut betrachtet
Eine palindromische Teilfolge ist eine Teilfolge (deren Elemente nicht unbedingt zusammenhängend sind), die vorwärts und rückwärts gleich gelesen wird. Ein palindromischer Teilstring muss aus zusammenhängenden Zeichen bestehen. Für 'bbbab' ist die längste palindromische Teilfolge 'bbbb' (Länge 4), während der längste palindromische Teilstring 'bbb' (Länge 3) ist. Diese beiden Probleme erfordern trotz ihrer ähnlichen Namen unterschiedliche Techniken.
Längste palindromische Teilfolge: LPS-Zustand
Definieren Sie dp[i][j] als die Länge der längsten palindromischen Teilfolge in s[i..j]. Die Rekurrenz lautet: Wenn s[i] == s[j] gilt, dann ist dp[i][j] = dp[i+1][j-1] + 2 (die beiden übereinstimmenden Zeichen erweitern das innere Palindrom). Andernfalls gilt dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (überspringen Sie das linke oder rechte Zeichen). Basisfall: dp[i][i] = 1 für jedes einzelne Zeichen.
s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')Füllreihenfolge und Implementierung von LPS
Wir füllen die LPS-Tabelle nach zunehmender Intervalllänge, nach demselben Muster wie bei allgemeiner Intervall-DP. Für jedes Intervall [i, j] der Länge 2 oder mehr prüfen wir, ob die beiden Randzeichen übereinstimmen, und wenden die Rekurrenz an. Das Endergebnis ist dp[0][n-1], die LPS der gesamten Zeichenkette.
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
inner = dp[i+1][j-1] if length > 2 else 0
dp[i][j] = inner + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
print(longest_palindromic_subsequence('bbbab')) # 4LPS über die LCS-Äquivalenz
Eine elegante Alternative: Die LPS der Zeichenkette s ist gleich der LCS von s und ihrer Umkehrung s[::-1]. Der Grund ist, dass jede palindromische Teilfolge von s eine gemeinsame Teilfolge von s und seiner Umkehrung ist. Dadurch können Sie Ihren LCS-Code direkt wiederverwenden. Für 'bbbab' lautet die Umkehrung 'babbb', und ihre LCS hat die Länge 4.
def lps_via_lcs(s):
t = s[::-1]
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[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]
print(lps_via_lcs('bbbab')) # 4Längster palindromischer Teilstring: Brute Force
Der längste palindromische Teilstring muss aus zusammenhängenden Zeichen bestehen. Ein Brute-Force-Ansatz prüft alle O(n²) Teilstrings und verifiziert jeden davon in O(n) Zeit – insgesamt O(n³). Es gibt zwei schnellere Ansätze: Intervall-DP mit O(n²) Zeit und Speicher sowie Ausdehnen vom Zentrum aus mit O(n²) Zeit, aber O(1) Speicher. In Interviews wird das Ausdehnen vom Zentrum aus bevorzugt, weil es einen kleineren konstanten Faktor und übersichtlicheren Code hat.
Intervall-DP für palindromische Teilstrings
Definieren Sie dp[i][j] = True, wenn s[i..j] ein Palindrom ist. Rekurrenz: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Basisfälle: dp[i][i] = True und dp[i][i+1] = (s[i] == s[i+1]). Verfolgen Sie die maximale Länge des gefundenen Palindroms. Füllen Sie die Tabelle nach zunehmender Länge. Dies benötigt O(n²) Zeit und O(n²) Speicher.
def longest_palindrome_dp(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start, max_len = i, 2
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start+max_len]
print(longest_palindrome_dp('babad')) # 'bab' or 'aba'Technik des Ausdehnens vom Zentrum aus
Der Ansatz des Ausdehnens vom Zentrum aus betrachtet jedes Zeichen (und jedes Paar benachbarter Zeichen) als mögliches Palindromzentrum und dehnt sich nach außen aus, solange beide Seiten übereinstimmen. Es gibt 2n-1 mögliche Zentren (n für Palindrome ungerader Länge, n-1 für Palindrome gerader Länge). Jede Ausdehnung benötigt höchstens O(n) Zeit, was insgesamt O(n²) bei O(1) Speicher ergibt – optimal für die meisten Interviewsituationen.
def longest_palindrome_expand(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1 # length of palindrome
start, max_len = 0, 1
for i in range(len(s)):
odd = expand(i, i) # odd-length
even = expand(i, i+1) # even-length
best = max(odd, even)
if best > max_len:
max_len = best
start = i - (best - 1) // 2
return s[start:start+max_len]
print(longest_palindrome_expand('cbbd')) # 'bb'Speicheroptimierung für LPS
Die LPS-Intervall-DP benötigt O(n²) Speicher. Wenn Sie nur die Länge (nicht die eigentliche Teilfolge) benötigen, können Sie den Speicherbedarf reduzieren, indem Sie beachten, dass dp[i][j] nur von dp[i+1][j-1], dp[i+1][j] und dp[i][j-1] abhängt. Durch das Wiederverwenden von Zeilen und das Speichern eines diagonalen Werts erreichen Sie O(n) Speicher – die Implementierung wird jedoch komplexer und ist in Interviews nur selten erforderlich.
LPS rekonstruieren
Um die tatsächliche palindromische Teilfolge zu rekonstruieren, verfolgen Sie die DP-Tabelle rückwärts. Beginnen Sie bei (0, n-1). Wenn s[i] == s[j] gilt, fügen Sie dieses Zeichen an beide Enden Ihres Ergebnisses an und gehen Sie zu (i+1, j-1) weiter. Andernfalls gehen Sie zu demjenigen von (i+1, j) oder (i, j-1) weiter, dessen Wert größer ist. Diese Greedy-Rückverfolgung rekonstruiert eindeutig eine optimale palindromische Teilfolge.
def reconstruct_lps(s, dp):
result = []
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
result.append(s[i])
i += 1; j -= 1
elif dp[i+1][j] > dp[i][j-1]:
i += 1
else:
j -= 1
# middle character for odd-length
mid = [s[i]] if i == j else []
return ''.join(result + mid + result[::-1])
print('Traceback recovers one optimal LPS')Zeitkomplexität von LPS und LCS vergleichen
Sowohl LPS über Intervall-DP als auch LCS benötigen O(n²) Zeit und O(n²) Speicher. Das Ausdehnen vom Zentrum aus für den längsten palindromischen Teilstring benötigt O(n²) Zeit, aber nur O(1) Speicher. Manachers Algorithmus löst das Teilstringproblem in O(n) Zeit und Speicher, ist jedoch so komplex, dass Interviewer ihn nur selten erwarten. In den meisten Interviewsituationen ist das Ausdehnen vom Zentrum aus die erwartete optimale Lösung für die Teilstring-Variante.
Häufige Fallstricke und Randfälle
Achten Sie auf diese Fallstricke: (1) Teilfolge und Teilzeichenkette zu verwechseln – es handelt sich um unterschiedliche Probleme mit unterschiedlichen Lösungen; (2) der Basisfall der Intervall-DP für Intervalle der Länge 2 erfordert eine Sonderbehandlung, da dp[i+1][j-1] gleich dp[i+1][i] wäre (leeres Intervall); (3) setzen Sie bei Expand-around-centre max_len = 1, da jedes einzelne Zeichen ein Palindrom ist; und (4) berechnen Sie beim Extrahieren des Ergebnisses start = i - (best-1)//2, um den Startindex anhand des Zentrums korrekt zu bestimmen.
Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Lektionszusammenfassung
In dieser Lektion haben Sie gelernt: LPS verwendet Intervall-DP mit der Rekurrenz dp[i][j] = dp[i+1][j-1]+2 bei übereinstimmenden Zeichen, die längste palindromische Teilzeichenkette lässt sich am besten mit Expand-around-centre in O(n²) Zeit und O(1) Speicherplatz finden und LPS entspricht der LCS aus der Zeichenkette und ihrer Umkehrung. Als Nächstes behandeln wir Palindrome Partitioning II, das eine Palindromtabelle mit 1D-DP für die minimale Anzahl an Schnitten kombiniert.
Häufig gestellte Fragen
Ist die Lektion „Längste palindromische Teilfolge und Teilzeichenkette“ kostenlos?
Ja — der vollständige Text von „Längste palindromische Teilfolge und Teilzeichenkette“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Längste palindromische Teilfolge und Teilzeichenkette“?
Wenden Sie Intervall-DP an, um die längste palindromische Teilfolge zu finden, und nutzen Sie den Trick des Ausdehnens um die Mitte für die längste palindromische Teilzeichenkette. Du übst Coding 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 Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding 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 palindromische Teilfolge und Teilzeichenkette“?
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 Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding 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
- Intervall-DP-Muster und Reihenfolge des Ausfüllens
- Längste palindromische Teilfolge und Teilzeichenkette
- Palindrome Partitioning II
- Burst Balloons: Umgekehrte Intervall-DP