Palindrom-partisjonering II
Kombiner en forhåndsberegnet palindromtabell med 1D-DP for å finne minste antall kutt som trengs for å dele en streng inn i palindromer.
Palindrom-partisjonering II er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Problem: Minimum antall kutt for partisjonering
Palindromisk partisjonering II spør: Gitt strengen s, finn det minste antallet kutt slik at hver delstreng i partisjoneringen er et palindrom. For 'aab' gir ett kutt ['aa', 'b'], så svaret er 1. For 'a' er svaret 0 (den er allerede et palindrom). Dette problemet kombinerer to DP-faser: Først forhåndsberegner vi hvilke delstrenger som er palindromer, og deretter bruker vi 1D-DP for å finne minimum antall kutt.
Fase 1: Forhåndsberegn palindromtabellen
Bygg først is_pal[i][j] = True når s[i..j] er et palindrom, ved hjelp av intervall-DP. Dette kjører på O(n²) tid og bruker O(n²) plass. Alternativt kan utvidelse rundt sentrum fylle ut den samme tabellen på O(n²) tid. Vi trenger denne tabellen fordi 1D-kutt-DP-en slår opp is_pal[i][j] gjentatte ganger — forhåndsberegning hindrer at palindromsjekker må beregnes på nytt inne i kutt-DP-løkken.
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'))Fase 2: Oppsett av 1D-kutt-DP
Definer cuts[i] som det minste antallet kutt for å partisjonere s[0..i]. Hvis s[0..i] selv er et palindrom, er cuts[i] = 0. Prøv ellers alle delinger: For hver j fra 0 til i-1, hvis s[j+1..i] er et palindrom, er cuts[i] = min(cuts[i], cuts[j] + 1). Spørsmålet er: Hva om den siste partisjonsdelen er s[j+1..i]? Da trenger vi cuts[j] kutt for prefikset, pluss ett kutt til.
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]Fullstendig løsning og gjennomgang
La oss gå gjennom 'aab'. Palindromtabell: 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. Kutt: cuts[0]=0 ('a' er et palindrom), cuts[1]=0 ('aa' er et palindrom), cuts[2]: 'aab' er ikke et palindrom, prøv j=1: is_pal[2][2]=T, så cuts[2] = cuts[1]+1 = 1. Svar: 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'))Tids- og plasskompleksitet
Fase 1 (palindromtabellen) kjører på O(n²) tid og bruker O(n²) plass. Fase 2 (kutt-DP) har en ytre løkke over n posisjoner og en indre løkke over n delingspunkter, altså også O(n²) tid. Totalt: O(n²) tid og O(n²) plass. Plassen kan reduseres til O(n) for cuts-tabellen, men palindromtabellen krever fortsatt O(n²). I intervjuer forventes O(n²) — en O(n)-løsning med Manachers algoritme ligger utenfor det typiske omfanget.
Utvidelse rundt sentrum for palindromtabellen
I stedet for intervall-DP-tilnærmingen for palindromtabellen kan De fylle ut is_pal ved hjelp av utvidelse rundt sentrum. For hver sentrumposisjon utvider De utover og markerer alle palindromene som finnes. Dette bruker fortsatt O(n²) tid og O(n²) plass, men kan være raskere i praksis på grunn av bedre cache-atferd. Begge tilnærmingene er gyldige i intervjuer.
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')Oppregning av alle partisjoneringer (del I)
Palindromisk partisjonering I (et beslektet problem) ber om å oppregne ALLE gyldige partisjoneringer der hver delstreng er et palindrom. Dette bruker tilbakesporing med den forhåndsberegnede palindromtabellen som en beskjæringsmekanisme. I motsetning til minimumskutt-DP-en, som teller, oppregner denne eksponentielt mange løsninger og løses med en helt annen tilnærming.
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']]Initialisering av cuts med n-1
Et vanlig triks er å initialisere cuts[i] = i i stedet for inf, siden verste tilfelle for s[0..i] er å kutte hvert tegn separat, noe som gir i kutt. Da slipper De å kontrollere om verdien er inf i koden. Når is_pal[0][i] er sann, overskrives verdien med 0. Denne initialiseringen tydeliggjør den øvre grensen for antall kutt og gjør koden litt enklere.
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]Alternativ: 1D-DP i én gjennomgang uten separat tabell
En elegant variant fyller ut palindromtabellen og kutt-DP-en samtidig. Når vi utvider palindromer fra hvert sentrum, oppdaterer vi cuts-tabellen umiddelbart. For et palindrom s[l..r] kan vi oppdatere cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). Dette unngår en separat O(n²)-gjennomgang av tabellen og kan være ryddigere å implementere under et intervju når tiden er knapp.
Kanttilfeller å ta hensyn til
Viktige kanttilfeller for palindromisk partisjonering II: (1) en streng med ett tegn gir 0 kutt; (2) en streng som allerede er et palindrom gir 0 kutt; (3) en streng med bare innbyrdes ulike tegn krever n-1 kutt; (4) en streng med identiske tegn (for eksempel 'aaaa') krever 0 kutt, siden hele strengen er et palindrom. Kontroller alltid at løsningen håndterer den tidlige avslutningen ved is_pal[0][i] = True korrekt.
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')) # 2Tips for kommunikasjon i intervju
Når De presenterer dette problemet i et intervju, bør De begynne med tilnærmingen i to faser: Bygg først palindromtabellen, og kjør deretter 1D-DP på kutt-tabellen. Forklar rekurrensen med ord før De skriver kode. Nevn at palindromtabellen har O(n²) oppføringer, og at hver av dem fylles ut på O(1) ved hjelp av rekurrensen for intervall-DP. Gå alltid gjennom sporingseksempelet før De skriver hele løsningen, slik at De demonstrerer korrekthet under tidspress.
Hurtigsjekk
Test forståelsen Deres av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Leksjonsoppsummering
I denne leksjonen lærte De: palindromisk partisjonering II bruker to DP-faser — forhåndsberegn palindromtabellen, og kjør deretter 1D-kutt-DP, kutt-rekurrensen er cuts[i] = min(cuts[j-1] + 1) for alle j der s[j..i] er et palindrom, og den totale kompleksiteten er O(n²) tid og O(n²) plass. I neste leksjon tar vi for oss Burst Balloons-problemet, som bruker en smart omvendt intervall-DP-tilnærming.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Palindrom-partisjonering II» gratis?
Ja – hele teksten i «Palindrom-partisjonering II» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Palindrom-partisjonering II»?
Kombiner en forhåndsberegnet palindromtabell med 1D-DP for å finne minste antall kutt som trengs for å dele en streng inn i palindromer. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «Palindrom-partisjonering II»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Intervall-DP-mønster og utfyllingsrekkefølge
- Lengste palindromiske delsekvens og delstreng
- Palindrom-partisjonering II
- Burst Balloons: Intervall-DP baklengs