Subsekuens dan Substring Palindromik Terpanjang
Terapkan DP interval untuk menemukan subsekuens palindromik terpanjang dan trik perluasan dari tengah untuk menemukan substring palindromik terpanjang
Subsekuens dan Substring Palindromik Terpanjang adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 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 DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Definisi Palindrom yang Ditinjau Kembali
Subsekuens palindromik adalah subsekuens (elemen yang tidak harus berurutan) yang dibaca sama dari depan maupun belakang. Subuntaian palindromik mengharuskan karakter-karakternya berurutan. Untuk 'bbbab', subsekuens palindromik terpanjang adalah 'bbbb' (panjang 4), sedangkan subuntaian palindromik terpanjang adalah 'bbb' (panjang 3). Kedua masalah ini memerlukan teknik yang berbeda meskipun namanya serupa.
Subsekuens Palindromik Terpanjang: Keadaan LPS
Definisikan dp[i][j] sebagai panjang subsekuens palindromik terpanjang dalam s[i..j]. Rumus rekurensinya adalah: jika s[i] == s[j], maka dp[i][j] = dp[i+1][j-1] + 2 (dua karakter yang sama memperluas palindrom bagian dalam). Jika tidak, dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (lewati karakter kiri atau kanan). Kasus dasar: dp[i][i] = 1 untuk semua karakter tunggal.
s = 'bbbab'
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
print('Base cases set, dp[i][i] = 1 for all i')Urutan Pengisian dan Implementasi LPS
Kita mengisi tabel LPS berdasarkan panjang rentang yang meningkat, dengan pola yang sama seperti DP Rentang umum. Untuk setiap rentang [i, j] dengan panjang 2 atau lebih, kita memeriksa apakah kedua karakter batasnya sama dan menerapkan rumus rekurensi. Jawaban akhirnya adalah dp[0][n-1], yaitu LPS dari seluruh untaian.
def longest_palindromic_subsequence(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
inner = dp[i+1][j-1] if length > 2 else 0
dp[i][j] = inner + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]
print(longest_palindromic_subsequence('bbbab')) # 4LPS melalui Kesetaraan LCS
Alternatif yang elegan: LPS dari untaian s sama dengan LCS dari s dan kebalikannya, s[::-1]. Hal ini karena setiap subsekuens palindromik dari s merupakan subsekuens bersama dari s dan kebalikannya. Reduksi ini memungkinkan Anda menggunakan kembali kode LCS secara langsung. Untuk 'bbbab', hasil pembalikannya adalah 'babbb', dan LCS keduanya adalah 4.
def lps_via_lcs(s):
t = s[::-1]
m, n = len(s), len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s[i-1] == t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
print(lps_via_lcs('bbbab')) # 4Subuntaian Palindromik Terpanjang: Pencarian Menyeluruh
Subuntaian palindromik terpanjang mengharuskan karakter-karakternya berurutan. Pendekatan pencarian menyeluruh memeriksa semua subuntaian O(n²) dan memverifikasi masing-masing dalam O(n) time—total O(n³). Ada dua pendekatan yang lebih cepat: DP Rentang dengan O(n²) time dan ruang, serta perluasan dari pusat dengan O(n²) time tetapi ruang O(1). Dalam wawancara, perluasan dari pusat lebih disukai karena konstanta waktunya lebih kecil dan kodenya lebih bersih.
DP Rentang untuk Subuntaian Palindromik
Definisikan dp[i][j] = True jika s[i..j] adalah palindrom. Rumus rekurensinya: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Kasus dasar: dp[i][i] = True dan dp[i][i+1] = (s[i] == s[i+1]). Catat panjang maksimum palindrom yang ditemukan. Isi berdasarkan urutan panjang yang meningkat. Algoritma ini berjalan dalam O(n²) time dan ruang O(n²).
def longest_palindrome_dp(s):
n = len(s)
dp = [[False]*n for _ in range(n)]
start, max_len = 0, 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start, max_len = i, 2
for length in range(3, n+1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if length > max_len:
start, max_len = i, length
return s[start:start+max_len]
print(longest_palindrome_dp('babad')) # 'bab' or 'aba'Teknik Perluasan dari Pusat
Pendekatan perluasan dari pusat mencoba setiap karakter (dan setiap pasangan karakter yang bersebelahan) sebagai pusat palindrom potensial, lalu memperluasnya ke arah luar selama kedua sisi cocok. Ada 2n-1 pusat yang mungkin (n untuk panjang ganjil, n-1 untuk panjang genap). Setiap perluasan memerlukan paling banyak O(n) time, sehingga totalnya O(n²) dengan ruang O(1)—optimal untuk sebagian besar situasi wawancara.
def longest_palindrome_expand(s):
def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1
r += 1
return r - l - 1 # length of palindrome
start, max_len = 0, 1
for i in range(len(s)):
odd = expand(i, i) # odd-length
even = expand(i, i+1) # even-length
best = max(odd, even)
if best > max_len:
max_len = best
start = i - (best - 1) // 2
return s[start:start+max_len]
print(longest_palindrome_expand('cbbd')) # 'bb'Optimisasi Ruang LPS
DP Rentang untuk LPS menggunakan ruang O(n²). Jika Anda hanya memerlukan panjang (bukan subsekuens sebenarnya), Anda dapat mengurangi ruang dengan mengamati bahwa dp[i][j] hanya bergantung pada dp[i+1][j-1], dp[i+1][j], dan dp[i][j-1]. Dengan menggunakan kembali baris dan menyimpan satu nilai diagonal, Anda dapat mencapai ruang O(n)—meskipun implementasinya lebih kompleks dan jarang diperlukan dalam wawancara.
Merekonstruksi LPS
Untuk merekonstruksi subsekuens palindromik sebenarnya, telusuri balik tabel DP. Mulailah dari (0, n-1). Jika s[i] == s[j], tambahkan karakter tersebut ke kedua ujung hasil Anda dan lanjutkan ke (i+1, j-1). Jika tidak, pindahlah ke salah satu dari (i+1, j) atau (i, j-1) yang memiliki nilai lebih besar. Penelusuran balik dengan memilih nilai terbesar ini memulihkan satu subsekuens palindromik optimal secara unik.
def reconstruct_lps(s, dp):
result = []
i, j = 0, len(s) - 1
while i < j:
if s[i] == s[j]:
result.append(s[i])
i += 1; j -= 1
elif dp[i+1][j] > dp[i][j-1]:
i += 1
else:
j -= 1
# middle character for odd-length
mid = [s[i]] if i == j else []
return ''.join(result + mid + result[::-1])
print('Traceback recovers one optimal LPS')Membandingkan Kompleksitas Waktu LPS dan LCS
Baik LPS melalui DP Rentang maupun LCS berjalan dalam O(n²) time dan ruang O(n²). Perluasan dari pusat untuk subuntaian palindromik terpanjang memiliki O(n²) time, tetapi hanya menggunakan ruang O(1). Algoritma Manacher menyelesaikan masalah subuntaian dalam O(n) time dan ruang, tetapi cukup kompleks sehingga pewawancara jarang mengharapkannya. Untuk sebagian besar konteks wawancara, perluasan dari pusat adalah solusi optimal yang diharapkan untuk varian subuntaian.
Jebakan Umum dan Kasus Tepi
Waspadai jebakan berikut: (1) mencampuradukkan suburutan dengan subteks — keduanya merupakan masalah yang berbeda dengan solusi yang berbeda; (2) kasus dasar DP interval untuk rentang dengan panjang 2 memerlukan penanganan khusus karena dp[i+1][j-1] akan menjadi dp[i+1][i] (rentang kosong); (3) untuk perluasan dari pusat, inisialisasi max_len = 1 (setiap karakter tunggal merupakan palindrom); dan (4) saat mengambil hasil, hitung start = i - (best-1)//2 untuk menemukan indeks awal dengan benar dari pusat.
Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritma — Persiapan Wawancara Pemrograman dari pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini, Anda mempelajari: LPS menggunakan DP interval dengan relasi dp[i][j] = dp[i+1][j-1]+2 ketika karakter cocok, subteks palindrom terpanjang paling baik diselesaikan dengan perluasan dari pusat dalam waktu O(n²) dan ruang O(1), dan LPS sama dengan LCS dari string dan kebalikannya. Selanjutnya kita akan membahas Partisi Palindrom II, yang menggabungkan tabel palindrom dengan DP 1D untuk potongan minimum.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Subsekuens dan Substring Palindromik Terpanjang” gratis?
Ya — teks lengkap “Subsekuens dan Substring Palindromik Terpanjang” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Subsekuens dan Substring Palindromik Terpanjang”?
Terapkan DP interval untuk menemukan subsekuens palindromik terpanjang dan trik perluasan dari tengah untuk menemukan substring palindromik terpanjang Kamu berlatih DSA 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 DSA Interview Prep?
Tidak diperlukan pengalaman sebelumnya. DSA 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 2 dari 4.
Berapa lama pelajaran “Subsekuens dan Substring Palindromik Terpanjang” 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 DSA Interview Prep ini?
Ya. Setiap pelajaran DSA 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