Partisi Palindrom II
Gabungkan tabel palindrom yang telah dihitung dengan DP 1D untuk menemukan jumlah pemotongan minimum yang diperlukan guna mempartisi sebuah String menjadi palindrom
Partisi Palindrom II adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Masalah: Potongan Minimum untuk Mempartisi
Partisi Palindrom II menanyakan: dengan string s yang diberikan, temukan jumlah potongan minimum sehingga setiap subteks dalam partisi merupakan palindrom. Untuk 'aab', satu potongan menghasilkan ['aa', 'b'], sehingga jawabannya adalah 1. Untuk 'a', jawabannya adalah 0 (sudah merupakan palindrom). Masalah ini menggabungkan dua fase DP: pertama, hitung terlebih dahulu subteks mana yang merupakan palindrom, lalu gunakan DP 1D untuk menemukan potongan minimum.
Fase 1: Menghitung Tabel Palindrom Terlebih Dahulu
Pertama, bangun is_pal[i][j] = True jika s[i..j] merupakan palindrom menggunakan DP interval. Proses ini berjalan dalam waktu O(n²) dan ruang O(n²). Sebagai alternatif, perluasan dari pusat mengisi tabel yang sama dalam waktu O(n²). Kita memerlukan tabel ini karena DP potongan 1D akan berkali-kali meminta nilai is_pal[i][j] — prakomputasi mencegah pemeriksaan palindrom dihitung ulang di dalam perulangan DP potongan.
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: Penyiapan DP Potongan 1D
Definisikan cuts[i] sebagai jumlah potongan minimum untuk mempartisi s[0..i]. Jika s[0..i] sendiri merupakan palindrom, cuts[i] = 0. Jika tidak, coba setiap pemisahan: untuk setiap j dari 0 hingga i-1, jika s[j+1..i] merupakan palindrom, maka cuts[i] = min(cuts[i], cuts[j] + 1). Pertanyaannya adalah: bagaimana jika bagian partisi terakhir adalah s[j+1..i]? Maka kita memerlukan cuts[j] potongan untuk awalan tersebut, ditambah 1 potongan lagi.
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]Solusi Lengkap dan Penelusuran
Mari kita telusuri 'aab'. Tabel palindrom: 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. Potongan: cuts[0]=0 ('a' adalah palindrom), cuts[1]=0 ('aa' adalah palindrom), cuts[2]: 'aab' bukan palindrom, coba j=1: is_pal[2][2]=T sehingga cuts[2] = cuts[1]+1 = 1. Jawaban: 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'))Kompleksitas Waktu dan Ruang
Fase 1 (tabel palindrom) berjalan dalam waktu O(n²) dan ruang O(n²). Fase 2 (DP potongan) memiliki perulangan luar atas n posisi dan perulangan dalam atas n titik pemisahan, sehingga juga memerlukan waktu O(n²). Secara keseluruhan: waktu O(n²), ruang O(n²). Ruang untuk larik potongan dapat dikurangi menjadi O(n), tetapi tabel palindrom tetap memerlukan O(n²). Pewawancara mengharapkan O(n²) — solusi O(n) menggunakan algoritma Manacher berada di luar cakupan yang umum.
Perluasan dari Pusat untuk Tabel Palindrom
Alih-alih menggunakan pendekatan DP interval untuk tabel palindrom, Anda dapat mengisi is_pal menggunakan perluasan dari pusat. Untuk setiap posisi pusat, perluas ke arah luar dan tandai semua palindrom yang ditemukan. Proses ini tetap memerlukan waktu O(n²) dan ruang O(n²), tetapi mungkin lebih cepat dalam praktik karena perilaku tembolok yang lebih baik. Kedua pendekatan valid dalam wawancara.
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')Mengenumerasi Semua Partisi (Bagian I)
Partisi Palindrom I (masalah terkait) meminta Anda mengenumerasi SEMUA partisi valid yang setiap subteksnya merupakan palindrom. Pendekatan ini menggunakan backtrack dengan tabel palindrom yang telah dihitung sebelumnya sebagai acuan pemangkasan. Berbeda dari DP potongan minimum yang melakukan penghitungan, pendekatan ini mengenumerasi solusi dalam jumlah eksponensial dan diselesaikan dengan pendekatan yang sepenuhnya berbeda.
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']]Menginisialisasi Potongan dengan n-1
Salah satu cara umum adalah menginisialisasi cuts[i] = i, bukan inf, karena kasus terburuk untuk s[0..i] adalah memotong setiap karakter secara terpisah, sehingga menghasilkan i potongan. Dengan demikian, Anda tidak perlu memeriksa inf dalam kode. Saat is_pal[0][i] bernilai true, tetapkan ulang nilainya menjadi 0. Inisialisasi ini memperjelas batas atas jumlah potongan dan sedikit menyederhanakan kode.
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]Alternatif: DP Satu Lintasan Tanpa Tabel Terpisah
Varian yang elegan mengisi tabel palindrom dan DP potongan secara bersamaan. Saat memperluas palindrom dari setiap pusat, kita langsung memperbarui larik cuts. Untuk palindrom s[l..r], kita dapat memperbarui cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)). Cara ini menghindari lintasan tabel O(n²) yang terpisah dan mungkin lebih rapi diterapkan selama wawancara ketika waktu terbatas.
Kasus Tepi yang Perlu Dipertimbangkan
Kasus tepi utama untuk Partisi Palindrom II: (1) string satu karakter menghasilkan 0 potongan; (2) string yang sudah merupakan palindrom menghasilkan 0 potongan; (3) string dengan semua karakter berbeda memerlukan n-1 potongan; (4) string dengan semua karakter sama (misalnya, 'aaaa') memerlukan 0 potongan karena seluruh string merupakan palindrom. Selalu pastikan solusi Anda menangani keluar lebih awal saat is_pal[0][i] = True dengan benar.
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')) # 2Kiat Komunikasi saat Wawancara
Saat memaparkan masalah ini dalam wawancara, mulailah dengan pendekatan dua fase: pertama, bangun tabel palindrom, lalu jalankan DP 1D pada larik potongan. Jelaskan relasi rekurensinya secara lisan sebelum menulis kode. Sebutkan bahwa tabel palindrom memiliki O(n²) entri dan setiap entri diisi dalam O(1) menggunakan relasi rekurensi DP interval. Selalu telusuri contoh Anda sebelum menulis solusi lengkap untuk menunjukkan kebenaran solusi saat berada di bawah tekanan.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini, Anda mempelajari: Partisi Palindrom II menggunakan dua fase DP — menghitung tabel palindrom terlebih dahulu, lalu menjalankan DP potongan 1D, relasi potongannya adalah cuts[i] = min(cuts[j-1] + 1) untuk semua j dengan s[j..i] yang merupakan palindrom, dan kompleksitas keseluruhannya adalah waktu O(n²) dan ruang O(n²). Selanjutnya kita akan membahas masalah Balon Meletus, yang menggunakan pendekatan DP interval terbalik yang cerdik.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Partisi Palindrom II” gratis?
Ya — teks lengkap “Partisi Palindrom II” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Partisi Palindrom II”?
Gabungkan tabel palindrom yang telah dihitung dengan DP 1D untuk menemukan jumlah pemotongan minimum yang diperlukan guna mempartisi sebuah String menjadi palindrom Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Partisi Palindrom II” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Pola DP Interval dan Urutan Pengisian
- Subsekuens dan Substring Palindromik Terpanjang
- Partisi Palindrom II
- Burst Balloons: DP Interval Terbalik