Subjujukan dan Subrentetan Palindrom Terpanjang
Gunakan DP selang untuk mencari subjujukan palindrom terpanjang dan helah mengembangkan sekitar pusat untuk mencari subrentetan palindrom terpanjang.
Subjujukan dan Subrentetan Palindrom Terpanjang ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Takrif Palindrom Dikaji Semula
Subjujukan palindrom ialah subsejukan (elemen tidak semestinya berturutan) yang dibaca sama dari hadapan dan belakang. Subrentetan palindrom memerlukan aksara yang berturutan. Bagi 'bbbab', subjujukan palindrom terpanjang ialah 'bbbb' (panjang 4), manakala subrentetan palindrom terpanjang ialah 'bbb' (panjang 3). Kedua-dua masalah ini memerlukan teknik yang berbeza walaupun namanya hampir sama.
Subjujukan Palindrom Terpanjang: Keadaan LPS
Takrifkan dp[i][j] sebagai panjang subjujukan palindrom terpanjang dalam s[i..j]. Rumus rekuren ialah: jika s[i] == s[j], maka dp[i][j] = dp[i+1][j-1] + 2 (dua aksara yang sepadan memanjangkan palindrom dalaman). Jika tidak, dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (langkau aksara kiri atau kanan). Kes asas: dp[i][i] = 1 untuk semua aksara 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')Susunan Pengisian dan Pelaksanaan LPS
Kita mengisi jadual LPS mengikut panjang selang yang semakin meningkat, iaitu corak yang sama seperti DP selang umum. Bagi setiap selang [i, j] yang panjangnya 2 atau lebih, kita menyemak sama ada kedua-dua aksara sempadan sepadan dan menggunakan rumus rekuren tersebut. Jawapan akhir ialah dp[0][n-1], iaitu LPS bagi keseluruhan rentetan.
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
Satu alternatif yang elegan: LPS bagi rentetan s adalah sama dengan LCS bagi s dan songsangan s[::-1]. Hal ini kerana mana-mana subjujukan palindrom bagi s ialah subsejukan sepunya bagi s dan songsangannya. Pengurangan ini membolehkan anda menggunakan semula kod LCS anda secara langsung. Bagi 'bbbab', rentetan songsangnya ialah 'babbb', dan LCS kedua-duanya ialah 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')) # 4Subrentetan Palindrom Terpanjang: Kaedah Cuba Semua Kemungkinan
Subrentetan palindrom terpanjang memerlukan aksara yang berturutan. Pendekatan cuba semua kemungkinan menyemak semua subrentetan O(n²) dan mengesahkan setiap satunya dalam O(n) time — jumlah O(n³). Dua pendekatan yang lebih pantas wujud: DP selang dalam O(n²) time dan ruang, serta pengembangan dari pusat dalam O(n²) time tetapi ruang O(1). Untuk temu duga, pengembangan dari pusat lebih disukai kerana pemalarnya lebih kecil dan kodnya lebih kemas.
DP Selang untuk Subrentetan Palindrom
Takrifkan dp[i][j] = True jika s[i..j] ialah palindrom. Rumus rekuren: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Kes asas: dp[i][i] = True dan dp[i][i+1] = (s[i] == s[i+1]). Jejaki palindrom yang mempunyai panjang maksimum. Isi jadual mengikut susunan panjang yang semakin meningkat. 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 Pengembangan dari Pusat
Pendekatan pengembangan dari pusat mencuba setiap aksara (dan setiap pasangan aksara bersebelahan) sebagai pusat palindrom yang berpotensi, lalu mengembang ke arah luar selagi kedua-dua sisi sepadan. Terdapat 2n-1 pusat yang mungkin (n untuk panjang ganjil, n-1 untuk panjang genap). Setiap pengembangan mengambil paling banyak O(n) time, lalu memberikan jumlah O(n²) dengan ruang O(1) — optimum untuk kebanyakan situasi temu duga.
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'Pengoptimuman Ruang LPS
DP selang LPS menggunakan ruang O(n²). Apabila anda hanya memerlukan panjang (bukan subjujukan sebenar), anda boleh mengurangkan ruang dengan memerhatikan bahawa dp[i][j] hanya bergantung pada dp[i+1][j-1], dp[i+1][j] dan dp[i][j-1]. Dengan menggunakan semula baris dan menyimpan satu nilai pepenjuru, anda boleh mencapai ruang O(n) — walaupun pelaksanaannya lebih rumit dan jarang diperlukan dalam temu duga.
Membina Semula LPS
Untuk membina semula subjujukan palindrom sebenar, jejaki kembali melalui jadual DP. Mulakan pada (0, n-1). Jika s[i] == s[j], tambahkan aksara itu pada kedua-dua hujung hasil anda dan beralih ke (i+1, j-1). Jika tidak, beralih ke salah satu daripada (i+1, j) atau (i, j-1) yang mempunyai nilai lebih besar. Jejak kembali tamak ini mendapatkan semula satu subjujukan palindrom optimum 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 Kerumitan Masa LPS dan LCS
Kedua-dua LPS melalui DP selang dan LCS berjalan dalam O(n²) time dan ruang O(n²). Pengembangan dari pusat untuk subrentetan palindrom terpanjang mengambil O(n²) time tetapi hanya ruang O(1). Algoritma Manacher menyelesaikan masalah subrentetan dalam O(n) time dan ruang, tetapi cukup rumit sehingga penemu duga jarang menjangkakannya. Dalam kebanyakan konteks temu duga, pengembangan dari pusat ialah penyelesaian optimum yang dijangka untuk variasi subrentetan.
Perangkap Umum dan Kes Tepi
Berhati-hatilah terhadap perangkap ini: (1) mengelirukan subjujukan dengan subrentetan — kedua-duanya ialah masalah yang berbeza dengan penyelesaian yang berbeza; (2) kes asas DP selang untuk selang panjang-2 memerlukan pengendalian khas kerana dp[i+1][j-1] akan menjadi dp[i+1][i] (selang kosong); (3) untuk pengembangan dari pusat, mulakan max_len = 1 (setiap aksara tunggal ialah palindrom); dan (4) semasa mengekstrak hasil, kira start = i - (best-1)//2 untuk mencari indeks permulaan dengan tepat daripada pusat.
Semakan Ringkas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini anda mempelajari: LPS menggunakan DP selang dengan hubungan rekursi dp[i][j] = dp[i+1][j-1]+2 apabila aksara sepadan, subrentetan palindrom terpanjang paling baik diselesaikan dengan pengembangan dari pusat dalam masa O(n²) dan ruang O(1), dan LPS bersamaan dengan LCS bagi rentetan dan rentetan terbaliknya. Seterusnya, kita akan membincangkan pembahagian palindrom II, yang menggabungkan jadual palindrom dengan DP 1D untuk mendapatkan pemotongan minimum.
Pelajari Python dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 30
- Pelajaran
- 120
Soalan Lazim
Adakah pelajaran “Subjujukan dan Subrentetan Palindrom Terpanjang” percuma?
Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Subjujukan dan Subrentetan Palindrom Terpanjang”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Subjujukan dan Subrentetan Palindrom Terpanjang”?
Gunakan DP selang untuk mencari subjujukan palindrom terpanjang dan helah mengembangkan sekitar pusat untuk mencari subrentetan palindrom terpanjang. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?
Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.
Berapa lamakah pelajaran “Subjujukan dan Subrentetan Palindrom Terpanjang” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?
Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Corak DP Selang dan Susunan Pengisian
- Subjujukan dan Subrentetan Palindrom Terpanjang
- Pembahagian Palindrom II
- Belon Meletup: DP Selang Songsang