Palindrome Partitioning II
Kombinér en forudberegnet palindromtabel med 1D-DP for at finde det minimale antal snit, der kræves for at opdele en streng i palindromer.
Palindrome Partitioning II er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Problem: Mindste antal snit til opdeling
Palindromopdeling II spørger: Givet strengen s, hvad er det mindste antal snit, så hver delstreng i opdelingen er et palindrom? For 'aab' giver ét snit ['aa', 'b'], så svaret er 1. For 'a' er svaret 0, fordi strengen allerede er et palindrom. Dette problem kombinerer to DP-faser: Beregn først, hvilke delstrenge der er palindromer, og brug derefter 1D-DP til at finde det mindste antal snit.
Fase 1: Forudberegn palindromtabellen
Opbyg først is_pal[i][j] = True, hvis s[i..j] er et palindrom, ved hjælp af interval-DP. Det tager O(n²)-tid og O(n²)-plads. Alternativt kan udvidelse omkring centrum udfylde den samme tabel i O(n²)-tid. Vi har brug for denne tabel, fordi 1D-DP'en for snittene gentagne gange slår op i is_pal[i][j] — forudberegning forhindrer, at palindromkontroller beregnes igen inde i løkken for snit-DP'en.
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'))Opsætning af 1D-DP for snit
Definér cuts[i] som det mindste antal snit til at opdele s[0..i]. Hvis s[0..i] selv er et palindrom, er cuts[i] = 0. Ellers prøver du alle opdelinger: For hvert j fra 0 til i-1 gælder det, at hvis s[j+1..i] er et palindrom, så er cuts[i] = min(cuts[i], cuts[j] + 1). Vi spørger altså: Hvad nu hvis det sidste stykke i opdelingen er s[j+1..i]? Så skal vi bruge cuts[j] snit til præfikset plus ét ekstra snit.
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]Fuld løsning og gennemgang
Lad os gennemgå 'aab'. Palindromtabel: 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. Snit: cuts[0]=0 ('a' er et palindrom), cuts[1]=0 ('aa' er et palindrom), cuts[2]: 'aab' er ikke et palindrom, så prøv j=1: is_pal[2][2]=T, og derfor er 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 pladskompleksitet
Fase 1 (palindromtabellen) tager O(n²)-tid og bruger O(n²)-plads. Fase 2 (snit-DP'en) har en ydre løkke over n positioner og en indre løkke over n opdelingspunkter, så den tager også O(n²)-tid. Samlet: O(n²)-tid og O(n²)-plads. Pladsforbruget kan reduceres til O(n) for snit-arrayet, men palindromtabellen kræver stadig O(n²). Interviewere forventer O(n²) — en O(n)-løsning med Manachers algoritme ligger uden for det typiske omfang.
Udvidelse omkring centrum til palindromtabellen
I stedet for interval-DP-tilgangen til palindromtabellen kan du udfylde is_pal ved hjælp af udvidelse omkring centrum. For hver centrumposition udvider du udad og markerer alle fundne palindromer. Det tager stadig O(n²)-tid og O(n²)-plads, men kan være hurtigere i praksis på grund af bedre cacheadfærd. Begge tilgange er gyldige til interviews.
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')Optælling af alle opdelinger (Del I)
Palindromopdeling I (et beslægtet problem) beder dig om at opregne ALLE gyldige opdelinger, hvor hver delstreng er et palindrom. Det bruger backtracking med den forudberegnede palindromtabel som grundlag for beskæring. I modsætning til minimum-snit-DP'en, som tæller, opregner denne tilgang eksponentielt mange løsninger og løses derfor på en helt anden måde.
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 af cuts med n-1
Et almindeligt kneb er at initialisere cuts[i] = i i stedet for inf, eftersom det værst tænkelige tilfælde for s[0..i] er at skære hvert tegn ud for sig, hvilket giver i snit. Det betyder, at du ikke behøver kontrollere for inf i koden. Når is_pal[0][i] er sand, overskriver vi værdien med 0. Denne initialisering tydeliggør den øvre grænse for antallet af snit og gør koden en smule 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: Én-gennemgangs-DP uden separat tabel
En elegant variant udfylder palindromtabellen og snit-DP'en samtidig. Mens vi udvider palindromer fra hvert centrum, opdaterer vi straks cuts-arrayet. For et palindrom s[l..r] kan vi opdatere cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). Det undgår en separat tabelgennemgang på O(n²) og kan være renere at implementere under en jobsamtale, når tiden er knap.
Kanttilfælde, du bør overveje
Vigtige kanttilfælde for palindromopdeling II: (1) en streng med ét tegn giver 0 snit; (2) en streng, der allerede er et palindrom, giver 0 snit; (3) en streng med kun forskellige tegn kræver n-1 snit; (4) en streng med kun ens tegn, f.eks. 'aaaa', kræver 0 snit, fordi hele strengen er et palindrom. Kontrollér altid, at din løsning håndterer den tidlige afslutning 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 til kommunikation i en jobsamtale
Når du præsenterer dette problem i en jobsamtale, skal du lægge ud med tilgangen i to faser: Opbyg først palindromtabellen, og kør derefter 1D-DP på snit-arrayet. Forklar rekurrensen med ord, før du koder. Nævn, at palindromtabellen har O(n²) poster, og at hver post udfyldes i O(1) ved hjælp af interval-DP-rekurrensen. Gennemgå altid dit eksempel, før du skriver den fulde løsning, så du demonstrerer korrektheden under tidspres.
Hurtigt tjek
Test din forståelse af begreberne Data Structures & Algorithms — Coding Interview Prep fra denne lektion.
Opsummering af lektionen
I denne lektion lærte du: palindromopdeling II bruger to DP-faser — først forudberegnes palindromtabellen, derefter køres 1D-snit-DP, snit-rekurrensen er cuts[i] = min(cuts[j-1] + 1) for alle j, hvor s[j..i] er et palindrom, og den samlede kompleksitet er O(n²)-tid og O(n²)-plads. Næste emne er problemet med at sprænge balloner, som bruger en smart omvendt interval-DP-tilgang.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Palindrome Partitioning II” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Palindrome Partitioning II”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Palindrome Partitioning II”?
Kombinér en forudberegnet palindromtabel med 1D-DP for at finde det minimale antal snit, der kræves for at opdele en streng i palindromer. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Palindrome Partitioning II”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Interval-DP-mønster og udfyldningsrækkefølge
- Længste palindromiske delsekvens og delstreng
- Palindrome Partitioning II
- Burst Balloons: Omvendt interval-DP