En Uzun Palindromik Alt Dizi ve Alt Metin
En uzun palindromik alt diziyi bulmak için aralık DP’yi, en uzun palindromik alt metni bulmak için merkezden dışa genişletme yöntemini uygulayın.
En Uzun Palindromik Alt Dizi ve Alt Metin, CoddyKit'te ücretsiz bir DSA Interview Prep dersidir. Bu, 4 dersinin 2. 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.
Palindrom Tanımlarını Yeniden İnceleme
Palindromik alt dizi, (öğelerin bitişik olması gerekmeden) baştan ve sondan aynı okunan bir alt dizidir. Palindromik alt dize ise karakterlerin bitişik olmasını gerektirir. 'bbbab' için en uzun palindromik alt dizi 'bbbb' (uzunluk 4), en uzun palindromik alt dize ise 'bbb' (uzunluk 3) olur. Benzer adlarına rağmen bu iki problem farklı teknikler gerektirir.
En Uzun Palindromik Alt Dizi: LPS Durumu
dp[i][j] değerini, s[i..j] içindeki en uzun palindromik alt dizinin uzunluğu olarak tanımlayın. Bağıntı şöyledir: s[i] == s[j] ise dp[i][j] = dp[i+1][j-1] + 2 olur (eşleşen iki karakter içteki palindromu genişletir). Aksi durumda dp[i][j] = max(dp[i+1][j], dp[i][j-1]) olur (sol veya sağ karakteri atlarız). Temel durum: tüm tek karakterler için dp[i][i] = 1.
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')LPS Doldurma Sırası ve Uygulaması
LPS tablosunu, genel aralık DP'sindeki örüntünün aynısı olan artan aralık uzunluğu sırasıyla doldururuz. Uzunluğu 2 veya daha fazla olan her [i, j] aralığı için iki sınır karakterinin eşleşip eşleşmediğini kontrol eder ve bağıntıyı uygularız. Son yanıt, dizenin tamamındaki LPS olan dp[0][n-1] değeridir.
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 ile LCS Eşdeğerliği
Zarif bir alternatif şudur: s dizesinin LPS'si, s ile tersinin s[::-1] LCS'sine eşittir. Bunun nedeni, s içindeki her palindromik alt dizinin s ve tersinin ortak alt dizisi olmasıdır. Bu dönüşüm, LCS kodunuzu doğrudan yeniden kullanmanızı sağlar. 'bbbab' dizisinin tersi 'babbb' olur ve bu iki dizenin LCS'si 4'tür.
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')) # 4En Uzun Palindromik Alt Dize: Kaba Kuvvet
En uzun palindromik alt dize bitişik karakterler gerektirir. Kaba kuvvet yaklaşımı, O(n²) alt dizenin tamamını kontrol eder ve her birini O(n) time karmaşıklığında doğrular — toplamda O(n³). Daha hızlı iki yaklaşım vardır: O(n²) time ve alan karmaşıklığında aralık DP'si ve O(n²) time, ancak O(1) alan karmaşıklığında merkezden dışa doğru genişletme. Mülakatlarda, sabit katsayısı daha küçük ve kodu daha temiz olduğu için merkezden dışa doğru genişletme tercih edilir.
Palindromik Alt Dize İçin Aralık DP
s[i..j] bir palindrom ise dp[i][j] = True olarak tanımlayın. Bağıntı: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Temel durumlar: dp[i][i] = True ve dp[i][i+1] = (s[i] == s[i+1]). Bulunan en uzun palindromun uzunluğunu takip edin. Artan uzunluk sırasıyla doldurun. Bu yaklaşım O(n²) time ve O(n²) alan karmaşıklığında çalışır.
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'Merkezden Dışa Doğru Genişletme Tekniği
Merkezden dışa doğru genişletme yaklaşımı, her karakteri ve her bitişik karakter çiftini olası bir palindrom merkezi olarak dener; iki taraf eşleştiği sürece dışa doğru genişler. 2n-1 olası merkez vardır (n tek uzunluklu, n-1 çift uzunluklu). Her genişletme en fazla O(n) time alır; böylece O(1) alanla toplam O(n²) elde edilir — çoğu mülakat ortamı için en iyi yaklaşımdır.
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'LPS Alan Optimizasyonu
LPS aralık DP'si O(n²) alan kullanır. Yalnızca uzunluğa (gerçek alt diziye değil) ihtiyacınız olduğunda, dp[i][j] değerinin yalnızca dp[i+1][j-1], dp[i+1][j] ve dp[i][j-1] değerlerine bağlı olduğunu gözlemleyerek alanı azaltabilirsiniz. Satırları yeniden kullanıp bir köşegen değerini kaydederek O(n) alan elde edebilirsiniz — ancak uygulama daha karmaşıktır ve mülakatlarda nadiren gerekir.
LPS'yi Yeniden Oluşturma
Gerçek palindromik alt diziyi yeniden oluşturmak için DP tablosunu geriye doğru izleyin. (0, n-1) konumundan başlayın. s[i] == s[j] ise bu karakteri sonucunuzun her iki ucuna ekleyin ve (i+1, j-1) konumuna ilerleyin. Aksi durumda, (i+1, j) veya (i, j-1) konumlarından daha büyük değere sahip olana ilerleyin. Bu açgözlü geriye izleme, en iyi palindromik alt dizilerden birini tek biçimde geri elde eder.
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')LPS ve LCS Zaman Karmaşıklığını Karşılaştırma
Hem aralık DP'siyle LPS hem de LCS O(n²) time ve O(n²) alan kullanır. En uzun palindromik alt dize için merkezden dışa doğru genişletme O(n²) time, ancak yalnızca O(1) alan kullanır. Manacher algoritması alt dize problemini O(n) time ve alan karmaşıklığında çözer, ancak mülakat yapanların nadiren bekleyeceği kadar karmaşıktır. Çoğu mülakat bağlamında, alt dize çeşidi için beklenen en iyi solution merkezden dışa doğru genişletmedir.
Yaygın Hatalar ve Uç Durumlar
Şu yaygın hatalara dikkat ediniz: (1) alt diziyi alt dizeyle karıştırmak — bunlar farklı çözümleri olan farklı problemlerdir; (2) uzunluğu 2 olan aralıklar için aralık DP'sinin temel durumu özel işlem gerektirir; çünkü dp[i+1][j-1], dp[i+1][i] (boş aralık) olur; (3) merkez etrafında genişletme için max_len = 1 değerini kullanınız (her tek karakter bir palindromdur); ve (4) sonucu çıkarırken, başlangıç dizinini merkezden doğru şekilde bulmak için start = i - (best-1)//2 değerini hesaplayınız.
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: LPS, karakterler eşleştiğinde dp[i][j] = dp[i+1][j-1]+2 bağıntısını kullanan aralık DP'sinden yararlanır, en uzun palindromik alt dize, O(n²) zamanda ve O(1) bellekle merkez etrafında genişletme kullanılarak en iyi şekilde bulunur ve LPS, dizenin kendisi ile tersinin LCS'sine eşittir. Sırada, bir palindrom tablosunu minimum kesim sayısı için 1B DP ile birleştiren Palindrom Parçalama II problemini ele alacağız.
Sıkça Sorulan Sorular
“En Uzun Palindromik Alt Dizi ve Alt Metin” dersi ücretsiz mi?
Evet — “En Uzun Palindromik Alt Dizi ve Alt Metin” 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.
“En Uzun Palindromik Alt Dizi ve Alt Metin” dersinde ne öğreneceğim?
En uzun palindromik alt diziyi bulmak için aralık DP’yi, en uzun palindromik alt metni bulmak için merkezden dışa genişletme yöntemini uygulayın. 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 2. dersidir.
“En Uzun Palindromik Alt Dizi ve Alt Metin” 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