Palindrom Bölümleme II
Bir metni palindromlara bölmek için gereken minimum kesme sayısını bulmak üzere önceden hesaplanmış palindrom tablosunu 1B DP ile birleştirin.
Palindrom Bölümleme II, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 3. dersidir. Aşağıdan dersin tamamını ücretsiz okuyabilir, sonra tarayıcıda yerleşik kod editörü ve 7/24 yapay zeka koçu ile uygulamalı olarak pratik yapabilirsin. Bu, DSA Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. DSA Interview Prep kursu toplamda 4 dersten oluşur.
Problem: Parçalamak İçin Minimum Kesim Sayısı
Palindrom Parçalama II şu soruyu sorar: s dizesi verildiğinde, parçalamadaki her alt dizenin palindrom olması için gereken minimum kesim sayısını bulunuz. 'aab' için tek bir kesimle ['aa', 'b'] elde edilir; dolayısıyla yanıt 1'dir. 'a' için yanıt 0'dır (dize zaten bir palindromdur). Bu problem iki DP aşamasını birleştirir: önce hangi alt dizelerin palindrom olduğunu önceden hesaplayın, ardından minimum kesim sayısını bulmak için 1B DP kullanın.
1. Aşama: Palindrom Tablosunu Önceden Hesaplama
Önce, aralık DP'sini kullanarak s[i..j] bir palindrom olduğunda is_pal[i][j] = True olacak şekilde tabloyu oluşturunuz. Bu işlem O(n²) zaman ve O(n²) bellek kullanır. Alternatif olarak merkez etrafında genişletme, aynı tabloyu O(n²) zamanda doldurur. Bu tabloya ihtiyaç duyarız; çünkü 1B kesim DP'si is_pal[i][j] değerini tekrar tekrar sorgular — tabloyu önceden hesaplamak, kesim DP döngüsü içinde palindrom kontrollerini yeniden yapmayı önler.
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'))2. Aşama: 1B Kesim DP'sini Kurma
cuts[i] değerini, s[0..i] dizesini parçalamak için gereken minimum kesim sayısı olarak tanımlayınız. s[0..i] kendi başına bir palindromsa cuts[i] = 0 olur. Aksi durumda her bölmeyi deneyiniz: 0'dan i-1'e kadar her j için, s[j+1..i] bir palindromsa cuts[i] = min(cuts[i], cuts[j] + 1) olur. Şunu soruyoruz: Son parçalama bölümü s[j+1..i] olursa ne olur? Bu durumda ön ek için cuts[j] kesime ve bir kesim daha eklemeye ihtiyaç duyarız.
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]Tam Çözüm ve Adım Adım İnceleme
'aab' örneğini adım adım inceleyelim. Palindrom tablosu: 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. Kesim sayıları: cuts[0]=0 ('a' bir palindromdur), cuts[1]=0 ('aa' bir palindromdur), cuts[2]: 'aab' bir palindrom değildir; j=1 için is_pal[2][2]=T olduğundan cuts[2] = cuts[1]+1 = 1 elde edilir. Yanıt: 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'))Zaman ve Bellek Karmaşıklığı
1. aşama (palindrom tablosu) O(n²) zaman ve O(n²) bellek kullanır. 2. aşamada (kesim DP'si), n konum üzerinde bir dış döngü ve n bölme noktası üzerinde bir iç döngü bulunur; dolayısıyla zaman karmaşıklığı yine O(n²)'dir. Genel olarak: O(n²) zaman, O(n²) bellek. Kesim dizisi için bellek kullanımı O(n)'e düşürülebilir; ancak palindrom tablosu yine O(n²) bellek gerektirir. Mülakatlarda O(n²) beklenir — Manacher algoritmasını kullanan O(n) çözüm, olağan kapsamın dışındadır.
Palindrom Tablosu için Merkez Etrafında Genişletme
Palindrom tablosu için aralık DP'si yaklaşımını kullanmak yerine is_pal tablosunu merkez etrafında genişletme yöntemiyle doldurabilirsiniz. Her merkez konumu için dışa doğru genişleyerek bulunan tüm palindromları işaretleyiniz. Bu yöntem de O(n²) zaman ve O(n²) bellek kullanır; ancak daha iyi önbellek davranışı sayesinde uygulamada daha hızlı olabilir. Her iki yaklaşım da mülakatlarda geçerlidir.
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')Tüm Parçalamaları Listeleme (Bölüm I)
Palindrom Parçalama I (ilgili bir problem), her alt dizenin palindrom olduğu geçerli ALL parçalamalarını listelemeyi ister. Bu işlem, önceden hesaplanmış palindrom tablosunu budama ölçütü olarak kullanan geri izleme yöntemiyle yapılır. Sayım yapan minimum kesim DP'sinin aksine bu yöntem üstel sayıda çözümü listeler ve tamamen farklı bir yaklaşımla çözülür.
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']]Kesim Sayısını n-1 ile Başlatma
Yaygın bir yöntem şudur: inf yerine cuts[i] = i değerini başlangıç olarak kullanınız; çünkü s[0..i] için en kötü durum, her karakteri ayrı ayrı kesmek ve i kesim elde etmektir. Böylece kodunuzda inf kontrolü yapmanız gerekmez. is_pal[0][i] doğru olduğunda değeri 0 ile değiştiririz. Bu başlatma, kesim sayısının üst sınırını netleştirir ve kodu biraz daha basitleştirir.
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: Ayrı Tablo Olmadan Tek Geçişli DP
Zarif bir seçenek, palindrom tablosunu ve kesim DP'sini eş zamanlı doldurur. Her merkezden palindromları genişletirken cuts dizisini hemen güncelleriz. s[l..r] bir palindrom olduğunda cuts[r] = min(cuts[r], (cuts[l-1]+1 if l > 0 else 0)) güncellemesini yapabiliriz. Bu yöntem ayrı bir O(n²)'lik tablo geçişini ortadan kaldırır ve zaman baskısı altındaki bir mülakatta uygulaması daha temiz olabilir.
Dikkate Alınması Gereken Uç Durumlar
Palindrom Parçalama II için önemli uç durumlar şunlardır: (1) tek karakterli dize 0 kesim döndürür; (2) zaten palindrom olan dize 0 kesim döndürür; (3) tüm karakterleri birbirinden farklı olan bir dize n-1 kesim gerektirir; (4) tüm karakterleri aynı olan bir dize (örneğin 'aaaa') 0 kesim gerektirir; çünkü dizenin tamamı bir palindromdur. Çözümünüzün is_pal[0][i] = True ile yapılan erken çıkışı doğru şekilde ele aldığını her zaman doğrulayınız.
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')) # 2Mülakat İletişimi İpuçları
Bu problemi bir mülakatta sunarken iki aşamalı yaklaşımla başlayınız: önce palindrom tablosunu oluşturun, ardından kesim dizisi üzerinde 1B DP çalıştırın. Kodlamaya başlamadan önce bağıntıyı sözlü olarak açıklayınız. Palindrom tablosunda O(n²) giriş bulunduğunu ve her birinin aralık DP'si bağıntısı kullanılarak O(1) zamanda doldurulduğunu belirtiniz. Doğruluğu baskı altında göstermek için tam çözümü yazmadan önce iz sürme örneğinizi her zaman adım adım inceleyiniz.
Hızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını anlayışınızı sınayınız.
Ders Özeti
Bu derste şunları öğrendiniz: Palindrom Parçalama II, iki DP aşaması kullanır — palindrom tablosunu önceden hesaplar, ardından 1B kesim DP'sini çalıştırır, kesim bağıntısı, s[j..i] bir palindrom olan tüm j değerleri için cuts[i] = min(cuts[j-1] + 1) şeklindedir ve genel karmaşıklık O(n²) zaman ve O(n²) bellektir. Sırada, akıllıca bir ters aralık DP'si yaklaşımı kullanan Balon Patlatma problemini ele alacağız.
Sıkça Sorulan Sorular
“Palindrom Bölümleme II” dersi ücretsiz mi?
Evet — “Palindrom Bölümleme II” dersin tüm metni burada web'de ücretsiz olarak okunabilir. Etkileşimli olarak pratik yapmak (yerleşik kod editörü ve 7/24 yapay zeka koçu) ve DSA Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. DSA Interview Prep kursu toplamda 4 dersten oluşur.
“Palindrom Bölümleme II” dersinde ne öğreneceğim?
Bir metni palindromlara bölmek için gereken minimum kesme sayısını bulmak üzere önceden hesaplanmış palindrom tablosunu 1B DP ile birleştirin. DSA Interview Prep ile uygulamalı kodu tarayıcıda doğrudan çalıştırarak pratik yaparsın ve 7/24 yapay zeka koçu dersi çalışırken sorularını yanıtlar.
DSA Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te DSA Interview Prep, başlangıçtan ileri seviyeye kadar yapılandırıldığı için buradan başlayabilir veya başından başlayıp kendi hızında ilerleme yapabilirsin. Bu, 4 dersinin 3. dersidir.
“Palindrom Bölümleme II” dersi ne kadar sürer?
Çoğu CoddyKit dersi yaklaşık 5–10 dakika sürer. Her biri kısa ve etkileşimli olduğu için sabit ilerleme yaparsın ve web ile uygulama arasında tam olarak bıraktığın yerden devam edebilirsin.
Bu DSA Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her DSA Interview Prep dersi yerleşik bir kod editörü içerir, bu sayede tarayıcıda gerçek kod yazıp çalıştırabilir ve anlık yapay zeka geri bildirimi alırsın — yerel kurulum gerekli değildir.
Bu kursun tüm dersleri
- Aralık DP Örüntüsü ve Doldurma Sırası
- En Uzun Palindromik Alt Dizi ve Alt Metin
- Palindrom Bölümleme II
- Balon Patlatma: Ters Aralık DP