En Uzun Ortak Alt Dizi
İki dizeyi bir DP tablosuyla hizalayın.
En Uzun Ortak Alt Dizi, CoddyKit'te ücretsiz bir Coding 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, Coding Interview Prep öğrenme yolunun bir parçasıdır ve ilerlemeniz web ve CoddyKit uygulaması arasında senkronize olur. Coding Interview Prep kursu toplamda 4 dersten oluşur.
Alt Dizinin Ne Olduğu
Bir alt dizi, karakterleri sırasını koruyarak içerir ancak bazılarını atlayabilir. 'abcde' içinden 'ace' alınabilir, ancak hiçbir zaman 'aec' alınamaz.
LCS Amacı
İki dize verildiğinde en uzun ortak alt dizi, her ikisinde de aynı göreli sırayla görünen en uzun dizidir.
Izgaraya Geçiş
İki dizenin öneklerini karşılaştırın. Uzunlukları üzerinde oluşturulan 2B bir tablo, bu problemi tanıdık bir ızgara DP'sine dönüştürür.
Durumu Tanımlama
dp[i][j], A'nın ilk i karakteriyle B'nin ilk j karakterinin LCS uzunluğu olsun.
Karakterler Eşleştiğinde
A[i-1], B[j-1]'e eşitse bu ortak harf LCS'yi uzatır. Köşegen dp[i-1][j-1] değerine bir eklersiniz.
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1Farklı Olduklarında
Harfler farklıysa dizelerden birinden bir karakter çıkarıp daha iyi sonucu koruyun. İki komşunun en büyüğünü seçersiniz.
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])Temel Durum
Boş bir öneğin ortak hiçbir şeyi yoktur; bu nedenle LCS uzunluğu sıfırdır. 0. satır ve 0. sütun tamamen sıfırlardan oluşur.
dp = [[0] * (m+1) for _ in range(n+1)]Bir Fazladan Satır ve Sütun
Tabloyu n+1'e m+1 boyutunda oluşturmak, ücretsiz bir sıfır sınırı sağlar. Böylece kenarlarda can sıkıcı sınır kontrolleri yapmanız gerekmez.
Doldurma
i ve j değerleri için 1'den başlayarak döngü kurun. Her hücrenin yalnızca üstteki, soldaki ve köşegen değerlerine ihtiyacı vardır; bunlar zaten hesaplanmıştır.
for i in range(1, n+1):
for j in range(1, m+1):
...Uzunluğu Okuma
Tam LCS uzunluğu köşede bulunur. Her hücre doldurulduğunda sonuç dp[n][m] değeridir.
length = dp[n][m]Karmaşıklık
Her hücreye bir kez baktığınız için çalışma süresi ve bellek kullanımı O(n çarpı m) olur. Bu, birkaç bin karaktere kadar olan dizeleri rahatça işler.
Hızlı Kontrol
Mevcut A[i-1] ve B[j-1] karakterleri eşit. Hangi güncelleme doğrudur?
Tekrar: LCS
n+1'e m+1 boyutunda bir tablo oluşturun: eşleşmede köşegen değere bir ekleyin, aksi halde en büyük komşuyu alın. Uzunluk köşede bulunur. 🔗
Sıkça Sorulan Sorular
“En Uzun Ortak Alt Dizi” dersi ücretsiz mi?
Evet — “En Uzun Ortak Alt Dizi” 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 Coding Interview Prep kursunun geri kalanını açmak için CoddyKit PRO'ya yükselt. Coding Interview Prep kursu toplamda 4 dersten oluşur.
“En Uzun Ortak Alt Dizi” dersinde ne öğreneceğim?
İki dizeyi bir DP tablosuyla hizalayın. Coding 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.
Coding Interview Prep öğrenmeye başlamak için deneyim gerekli mi?
Önceden deneyim gerekmez. CoddyKit'te Coding 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.
“En Uzun Ortak Alt Dizi” 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 Coding Interview Prep dersinde kod yazıp çalıştırabilir miyim?
Evet. Her Coding 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
- Izgarada Yol Sayma
- Engellerle Minimum Yol Toplamı
- En Uzun Ortak Alt Dizi
- Adım Adım Düzenleme Mesafesi