Palindrome Partitioning II
Kombinieren Sie eine vorab berechnete Palindromtabelle mit eindimensionaler DP, um die minimale Anzahl an Schnitten zu finden, die eine Zeichenkette in Palindrome aufteilen.
Palindrome Partitioning II ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 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.
Problem: Minimale Anzahl an Schnitten für die Partitionierung
Palindrome Partitioning II stellt folgende Aufgabe: Gegeben sei die Zeichenkette s. Finden Sie die minimale Anzahl an Schnitten, sodass jede Teilzeichenkette der Partition ein Palindrom ist. Für 'aab' genügt ein Schnitt: ['aa', 'b']; die Antwort ist also 1. Für 'a' lautet die Antwort 0, da die Zeichenkette bereits ein Palindrom ist. Dieses Problem kombiniert zwei DP-Phasen: Zuerst wird vorab berechnet, welche Teilzeichenketten Palindrome sind, anschließend werden mit 1D-DP die minimale Anzahl an Schnitten bestimmt.
Phase 1: Palindromtabelle vorab berechnen
Erstellen Sie zunächst mithilfe von Intervall-DP is_pal[i][j] = True, wenn s[i..j] ein Palindrom ist. Dies benötigt O(n²) Zeit und O(n²) Speicherplatz. Alternativ kann Expand-around-centre dieselbe Tabelle in O(n²) Zeit füllen. Wir benötigen diese Tabelle, weil die 1D-Schnitt-DP wiederholt is_pal[i][j] abfragt – durch die Vorberechnung vermeiden wir, die Palindromprüfungen innerhalb der Schleife der Schnitt-DP erneut durchzuführen.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
print(build_palindrome_table('aab'))Phase 2: 1D-Schnitt-DP einrichten
Definieren Sie cuts[i] als die minimale Anzahl an Schnitten, um s[0..i] zu partitionieren. Wenn s[0..i] selbst ein Palindrom ist, gilt cuts[i] = 0. Andernfalls probieren Sie jede mögliche Aufteilung: Für jedes j von 0 bis i-1 gilt, falls s[j+1..i] ein Palindrom ist, cuts[i] = min(cuts[i], cuts[j] + 1). Die Frage lautet: Was ist, wenn das letzte Partitionselement s[j+1..i] ist? Dann benötigen wir für das Präfix cuts[j] Schnitte plus einen weiteren Schnitt.
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0 # entire prefix is a palindrome
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]Vollständige Lösung und Ablauf
Betrachten wir 'aab' Schritt für Schritt. Palindromtabelle: is_pal[0][0]='a'=T, is_pal[1][1]='a'=T, is_pal[2][2]='b'=T, is_pal[0][1]='aa'=T, is_pal[1][2]='ab'=F, is_pal[0][2]='aab'=F. Schnitte: cuts[0]=0 ('a' ist ein Palindrom), cuts[1]=0 ('aa' ist ein Palindrom), cuts[2]: 'aab' ist kein Palindrom; für j=1 gilt: is_pal[2][2]=T, also cuts[2] = cuts[1]+1 = 1. Antwort: 1.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = [float('inf')] * n
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(i):
if is_pal[j+1][i]:
cuts[i] = min(cuts[i], cuts[j] + 1)
return cuts[n-1]
print(min_cut('aab')) # 1
print(min_cut('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab'))Zeit- und Speicherkomplexität
Phase 1 (Palindromtabelle) benötigt O(n²) Zeit und O(n²) Speicherplatz. Phase 2 (Schnitt-DP) enthält eine äußere Schleife über n Positionen und eine innere Schleife über n mögliche Schnittpunkte und benötigt daher ebenfalls O(n²) Zeit. Insgesamt ergibt sich: O(n²) Zeit, O(n²) Speicherplatz. Der Speicherbedarf für das Schnitt-Array lässt sich auf O(n) reduzieren, die Palindromtabelle benötigt jedoch weiterhin O(n²). In Interviews wird O(n²) erwartet – eine O(n)-Lösung mit Manachers Algorithmus geht über den üblichen Umfang hinaus.
Expand-around-centre für die Palindromtabelle
Statt des Intervall-DP-Ansatzes für die Palindromtabelle können Sie is_pal mit Expand-around-centre füllen. Erweitern Sie für jede Zentrumposition nach außen und markieren Sie alle gefundenen Palindrome. Dies benötigt weiterhin O(n²) Zeit und O(n²) Speicherplatz, kann in der Praxis aber aufgrund eines besseren Cache-Verhaltens schneller sein. Beide Ansätze sind in Interviews gültig.
def build_pal_expand(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
def expand(l, r):
while l >= 0 and r < n and s[l] == s[r]:
is_pal[l][r] = True
l -= 1; r += 1
for i in range(n):
expand(i, i) # odd-length centres
expand(i, i+1) # even-length centres
return is_pal
print('Expand-around-centre palindrome table built')Alle Partitionierungen aufzählen (Teil I)
Palindrome Partitioning I (ein verwandtes Problem) verlangt, ALLE gültigen Partitionierungen aufzuzählen, bei denen jede Teilzeichenkette ein Palindrom ist. Dazu wird Backtracking verwendet, wobei die vorab berechnete Palindromtabelle als Pruning-Hilfe dient. Im Gegensatz zur DP für die minimale Anzahl an Schnitten, die zählt, werden hierbei exponentiell viele Lösungen aufgezählt; deshalb wird ein vollständig anderer Ansatz verwendet.
def partition_all(s):
n = len(s)
is_pal = build_pal_expand(s)
result = []
def backtrack(start, path):
if start == n:
result.append(path[:])
return
for end in range(start, n):
if is_pal[start][end]:
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
backtrack(0, [])
return result
print(partition_all('aab')) # [['a','a','b'], ['aa','b']]cuts mit n-1 initialisieren
Ein verbreiteter Trick: Initialisieren Sie cuts[i] = i statt mit inf, da der schlechteste Fall für s[0..i] darin besteht, jedes Zeichen einzeln abzutrennen, wofür i Schnitte erforderlich sind. Dadurch entfällt die Prüfung auf inf im Code. Wenn is_pal[0][i] wahr ist, überschreiben wir den Wert mit 0. Diese Initialisierung macht die obere Schranke für die Anzahl der Schnitte deutlich und vereinfacht den Code geringfügig.
def min_cut_clean(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n)) # cuts[i] = i (worst case)
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]Alternative: One-Pass-DP ohne separate Tabelle
Eine elegante Variante füllt die Palindromtabelle und die Schnitt-DP gleichzeitig. Während wir die Palindrome von jedem Zentrum aus erweitern, aktualisieren wir sofort das Array cuts. Für ein Palindrom s[l..r] können wir cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)) aktualisieren. Dadurch entfällt ein separater O(n²)-Tabellendurchlauf, und die Implementierung kann in einem Interview unter Zeitdruck übersichtlicher sein.
Zu berücksichtigende Randfälle
Wichtige Randfälle für Palindrome Partitioning II: (1) Eine Zeichenkette mit nur einem Zeichen liefert 0 Schnitte; (2) eine Zeichenkette, die bereits ein Palindrom ist, liefert 0 Schnitte; (3) eine Zeichenkette mit ausschließlich unterschiedlichen Zeichen benötigt n-1 Schnitte; (4) eine Zeichenkette mit ausschließlich gleichen Zeichen (z. B. 'aaaa') benötigt 0 Schnitte, da die gesamte Zeichenkette ein Palindrom ist. Überprüfen Sie stets, dass Ihre Lösung den vorzeitigen Abbruch bei is_pal[0][i] = True korrekt verarbeitet.
def build_palindrome_table(s):
n = len(s)
is_pal = [[False]*n for _ in range(n)]
for i in range(n):
is_pal[i][i] = True
for i in range(n-1):
is_pal[i][i+1] = (s[i] == s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = (s[i] == s[j]) and is_pal[i+1][j-1]
return is_pal
def min_cut(s):
n = len(s)
is_pal = build_palindrome_table(s)
cuts = list(range(n))
for i in range(n):
if is_pal[0][i]:
cuts[i] = 0
else:
for j in range(1, i+1):
if is_pal[j][i]:
cuts[i] = min(cuts[i], cuts[j-1] + 1)
return cuts[n-1]
print(min_cut('a')) # 0
print(min_cut('aaaa')) # 0
print(min_cut('abc')) # 2Tipps zur Kommunikation im Interview
Beginnen Sie bei der Vorstellung dieses Problems im Interview mit dem Zwei-Phasen-Ansatz: Erstellen Sie zuerst die Palindromtabelle und führen Sie anschließend 1D-DP auf dem Schnitt-Array aus. Erklären Sie die Rekurrenz vor dem Programmieren in Worten. Erwähnen Sie, dass die Palindromtabelle O(n²) Einträge enthält und jeder Eintrag mithilfe der Rekurrenz der Intervall-DP in O(1) gefüllt wird. Gehen Sie stets Ihr Beispiel Schritt für Schritt durch, bevor Sie die vollständige Lösung schreiben, um auch unter Zeitdruck die Korrektheit zu demonstrieren.
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: Palindrome Partitioning II verwendet zwei DP-Phasen – zunächst wird die Palindromtabelle vorab berechnet, anschließend wird 1D-Schnitt-DP ausgeführt, die Rekurrenz für die Schnitte lautet cuts[i] = min(cuts[j-1] + 1) für alle j, für die s[j..i] ein Palindrom ist und die Gesamtkomplexität beträgt O(n²) Zeit und O(n²) Speicherplatz. Als Nächstes behandeln wir das Problem Burst Balloons, das einen cleveren Ansatz mit umgekehrter Intervall-DP verwendet.
Lerne Python mit einem KI-Tutor — kostenlos
Schreibe und führe echten Code in deinem Browser aus, bekomme sofortige Hilfe von einem 24/7 KI-Tutor und setze dein Lernen im Web oder in der App fort.
- Kurse
- 30
- Lektionen
- 120
Häufig gestellte Fragen
Ist die Lektion „Palindrome Partitioning II“ kostenlos?
Ja — der vollständige Text von „Palindrome Partitioning II“ 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 „Palindrome Partitioning II“?
Kombinieren Sie eine vorab berechnete Palindromtabelle mit eindimensionaler DP, um die minimale Anzahl an Schnitten zu finden, die eine Zeichenkette in Palindrome aufteilen. 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 3 von 4.
Wie lange dauert die Lektion „Palindrome Partitioning II“?
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
- Intervall-DP-Muster und Reihenfolge des Ausfüllens
- Längste palindromische Teilfolge und Teilzeichenkette
- Palindrome Partitioning II
- Burst Balloons: Umgekehrte Intervall-DP