Dzielenie palindromu II
Łączyć wstępnie obliczoną tablicę palindromów z jednowymiarowym DP, aby znaleźć minimalną liczbę cięć potrzebnych do podzielenia napisu na palindromy
Dzielenie palindromu II to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem: minimalna liczba cięć potrzebnych do podziału
Palindrome Partitioning II polega na znalezieniu dla danego łańcucha s minimalnej liczby cięć, tak aby każdy podłańcuch w podziale był palindromem. Dla 'aab' wystarczy jedno cięcie, które daje ['aa', 'b'], więc odpowiedź wynosi 1. Dla 'a' odpowiedź wynosi 0 (łańcuch jest już palindromem). Problem ten łączy dwa etapy DP: najpierw należy wstępnie obliczyć, które podłańcuchy są palindromami, a następnie użyć jednowymiarowego DP do znalezienia minimalnej liczby cięć.
Etap 1: wstępne obliczenie tabeli palindromów
Najpierw zbuduj is_pal[i][j] = True, jeśli s[i..j] jest palindromem, korzystając z programowania dynamicznego na przedziałach. Działanie to zajmuje O(n²) czasu i O(n²) pamięci. Alternatywnie można wypełnić tę samą tabelę metodą rozszerzania wokół środka w czasie O(n²). Tabela jest potrzebna, ponieważ jednowymiarowe DP cięć będzie wielokrotnie odwoływać się do is_pal[i][j] — wstępne obliczenie pozwala uniknąć ponownego sprawdzania palindromów wewnątrz pętli DP cięć.
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'))Etap 2: konfiguracja jednowymiarowego DP cięć
Zdefiniuj cuts[i] jako minimalną liczbę cięć potrzebnych do podziału s[0..i]. Jeśli s[0..i] samo jest palindromem, cuts[i] = 0. W przeciwnym razie wypróbuj każdy podział: dla każdego j od 0 do i-1, jeśli s[j+1..i] jest palindromem, wówczas cuts[i] = min(cuts[i], cuts[j] + 1). Pytamy w ten sposób: co się stanie, jeśli ostatnim fragmentem podziału będzie s[j+1..i]? Wtedy dla prefiksu potrzebujemy cuts[j] cięć oraz jeszcze jednego cięcia.
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]Pełne rozwiązanie i prześledzenie
Prześledźmy przykład 'aab'. Tabela palindromów: 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. Cięcia: cuts[0]=0 ('a' jest palindromem), cuts[1]=0 ('aa' jest palindromem), cuts[2]: 'aab' nie jest palindromem, więc dla j=1: is_pal[2][2]=T, zatem cuts[2] = cuts[1]+1 = 1. Odpowiedź: 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'))Złożoność czasowa i pamięciowa
Etap 1 (tabela palindromów) zajmuje O(n²) czasu i O(n²) pamięci. Etap 2 (DP cięć) ma zewnętrzną pętlę przechodzącą po n pozycjach oraz wewnętrzną pętlę przechodzącą po n punktach podziału, więc również zajmuje O(n²) czasu. Łącznie: O(n²) czasu, O(n²) pamięci. Pamięć dla tablicy cuts można zmniejszyć do O(n), ale tabela palindromów nadal wymaga O(n²). Podczas rozmowy rekrutacyjnej oczekuje się rozwiązania O(n²) — rozwiązanie O(n) wykorzystujące algorytm Manachera wykracza poza typowy zakres.
Rozszerzanie wokół środka w celu utworzenia tabeli palindromów
Zamiast podejścia opartego na programowaniu dynamicznym na przedziałach tabelę palindromów można wypełnić za pomocą rozszerzania wokół środka. Dla każdej pozycji będącej środkiem rozszerzaj zakres na zewnątrz i oznaczaj wszystkie znalezione palindromy. Nadal zajmuje to O(n²) czasu i O(n²) pamięci, ale w praktyce może działać szybciej dzięki lepszemu wykorzystaniu pamięci podręcznej. Oba podejścia są poprawne podczas rozmowy rekrutacyjnej.
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')Wyliczanie wszystkich podziałów (część I)
Palindrome Partitioning I (pokrewny problem) polega na wyliczeniu WSZYSTKICH poprawnych podziałów, w których każdy podłańcuch jest palindromem. Wykorzystuje się tu przeszukiwanie z nawrotami oraz wstępnie obliczoną tabelę palindromów do przycinania drzewa wyszukiwania. W przeciwieństwie do DP minimalnej liczby cięć, które zlicza rozwiązania, to podejście wylicza ich wykładniczo wiele i wymaga zupełnie innej metody.
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']]Inicjalizacja cuts wartością n-1
Często stosowana sztuczka polega na zainicjalizowaniu cuts[i] = i zamiast inf, ponieważ w najgorszym przypadku dla s[0..i] każdy znak trzeba oddzielić osobnym cięciem, co daje i cięć. Dzięki temu nie trzeba sprawdzać w kodzie wartości inf. Gdy is_pal[0][i] ma wartość true, nadpisujemy wynik wartością 0. Taka inicjalizacja jasno określa górne ograniczenie liczby cięć i nieco upraszcza kod.
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]Alternatywa: jednoprzebiegowe DP bez osobnej tabeli
Elegancki wariant jednocześnie wypełnia tabelę palindromów i wykonuje DP cięć. Podczas rozszerzania palindromów od każdego środka od razu aktualizujemy tablicę cuts. Dla palindromu s[l..r] możemy zaktualizować cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). Pozwala to pominąć osobne przejście po tabeli O(n²) i może ułatwić implementację podczas rozmowy rekrutacyjnej, gdy czas jest ograniczony.
Przypadki brzegowe, które należy uwzględnić
Najważniejsze przypadki brzegowe w problemie Palindrome Partitioning II: (1) łańcuch jednoznakowy wymaga 0 cięć; (2) łańcuch, który już jest palindromem, wymaga 0 cięć; (3) łańcuch złożony wyłącznie z różnych znaków wymaga n-1 cięć; (4) łańcuch złożony z jednakowych znaków (np. 'aaaa') wymaga 0 cięć, ponieważ cały łańcuch jest palindromem. Należy zawsze sprawdzić, czy rozwiązanie poprawnie obsługuje wczesne zakończenie po stwierdzeniu, że is_pal[0][i] = True.
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')) # 2Wskazówki dotyczące komunikacji podczas rozmowy rekrutacyjnej
Podczas przedstawiania tego problemu na rozmowie rekrutacyjnej należy zacząć od podejścia dwuetapowego: najpierw zbudować tabelę palindromów, a następnie wykonać jednowymiarowe DP na tablicy cięć. Przed rozpoczęciem kodowania należy słownie wyjaśnić rekurencję. Warto wspomnieć, że tabela palindromów zawiera O(n²) wpisów, a każdy z nich jest wypełniany w czasie O(1) na podstawie rekurencji DP na przedziałach. Przed napisaniem pełnego rozwiązania należy zawsze prześledzić przykład, aby pod presją zademonstrować jego poprawność.
Szybki test
Sprawdź swoje zrozumienie koncepcji Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji poznali Państwo: Palindrome Partitioning II wykorzystuje dwa etapy DP — wstępne obliczenie tabeli palindromów, a następnie jednowymiarowe DP cięć, rekurencja cięć ma postać cuts[i] = min(cuts[j-1] + 1) dla każdego j, dla którego s[j..i] jest palindromem oraz łączna złożoność wynosi O(n²) czasu i O(n²) pamięci. W następnej lekcji zajmiemy się problemem Burst Balloons, który wykorzystuje pomysłowe podejście oparte na odwróconym DP na przedziałach.
Często zadawane pytania
Czy lekcja „Dzielenie palindromu II” jest bezpłatna?
Tak — pełny tekst „Dzielenie palindromu II” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Dzielenie palindromu II”?
Łączyć wstępnie obliczoną tablicę palindromów z jednowymiarowym DP, aby znaleźć minimalną liczbę cięć potrzebnych do podzielenia napisu na palindromy Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.
Ile czasu zajmuje lekcja „Dzielenie palindromu II”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Schemat przedziałowego DP i kolejność wypełniania
- Najdłuższy palindromiczny podciąg i podłańcuch
- Dzielenie palindromu II
- Burst Balloons: odwrócone przedziałowe DP