En Uzun Ortak Alt Dizi
İki dize için LCS bağıntısını tanımlayın, iki boyutlu tabloyu doldurun ve tabloda geriye doğru iz sürerek gerçek alt diziyi yeniden oluşturun.
En Uzun Ortak Alt Dizi, CoddyKit'te ücretsiz bir Coding 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, 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 Dizi Nedir?
Bir dizgenin alt dizisi, kalan karakterlerin sırasını değiştirmeden bazı karakterlerin (veya hiçbir karakterin) silinmesiyle oluşturulur. Örneğin 'ACE', 'ABCDE' dizgesinin bir alt dizisidir; ancak 'AEC' değildir (sıra bozulmuştur). İki dizgenin En Uzun Ortak Alt Dizisi (LCS), her ikisinde de bulunan en uzun alt dizidir. 'ABCBDAB' ve 'BDCABA', uzunluğu 4 olan 'BCBA' veya 'BDAB' LCS'sini paylaşır.
# Subsequence vs Substring
# 'ACE' is a subsequence of 'ABCDE' (skip B, D)
# 'ACE' is NOT a substring of 'ABCDE' (must be contiguous)
# LCS examples:
# LCS('ABCBDAB', 'BDCABA') = 4 ('BCBA' or 'BDAB')
# LCS('AGGTAB', 'GXTXAYB') = 4 ('GTAB')
# LCS('ABC', 'AC') = 2 ('AC')
print('Subsequence check: ACE in ABCDE')
text = 'ABCDE'
pattern = 'ACE'
i = 0
for ch in text:
if i < len(pattern) and ch == pattern[i]: i += 1
print('Found:', i == len(pattern)) # TrueLCS Yineleme Bağıntısının Türetilmesi
dp[i][j] değerini text1[:i] ve text2[:j] dizgelerinin LCS uzunluğu olarak tanımlayın. Karakterler eşleşirse (text1[i-1] == text2[j-1]), LCS'yi 1 uzatırız: dp[i][j] = dp[i-1][j-1] + 1. Eşleşmezlerse, dizgelerden birinden bir karakter atlayarak elde edilen daha iyi sonucu seçeriz: dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Temel durum: dp[0][j] = dp[i][0] = 0 (boş dizgeyle LCS uzunluğu 0'dır).
def lcs_length(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 # extend match
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) # skip one
return dp[m][n]
print(lcs_length('ABCBDAB', 'BDCABA')) # 4
print(lcs_length('AGGTAB', 'GXTXAYB')) # 4
print(lcs_length('ABC', 'AC')) # 2LCS Tablosunu İzleme
text1='ABCD' ve text2='ACBD' için: Tüm değerleri sıfırla başlayın. Karakterler eşleştiğinde (A-A, C-C, doğru konumdaysa B-B, D-D), dp[i][j] = dp[i-1][j-1] + 1 olur. Aksi hâlde soldaki ve üstteki komşuların maksimumunu alın. Doldurulmuş tabloyu izlemek, köşegen adımların eşleşen karakterlere nasıl karşılık geldiğini gösterir. Son değer olan dp[4][4], LCS uzunluğunu verir.
def lcs_trace(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Print table
print(' ', ' '.join(text2))
for i, row in enumerate(dp):
label = ' ' if i == 0 else text1[i-1]
print(label, row)
return dp[m][n]
lcs_trace('ABCD', 'ACBD')Gerçek LCS'nin Yeniden Oluşturulması
Gerçek LCS dizesini elde etmek için dp[m][n] değerinden başlayarak DP tablosunda geriye doğru ilerleyin. Eğer text1[i-1] == text2[j-1] ise bu karakter LCS'nin içindedir; karakteri kaydedip (i-1, j-1) konumuna çapraz ilerleyin. Eğer dp[i-1][j] > dp[i][j-1] ise yukarı, aksi hâlde sola ilerleyin. Geriye doğru ilerlediğiniz için, sonunda topladığınız karakterleri ters çevirin. Bu yeniden oluşturma O(m+n) zamanda çalışır.
def lcs_reconstruct(text1, text2):
m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Backtrack
result = []
i, j = m, n
while i > 0 and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1; j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_reconstruct('ABCBDAB', 'BDCABA')) # BCBA or BDABO(n) Bellek Kullanımına Optimizasyon
LCS tablosunda yalnızca geçerli ve önceki satır gerekir. n+1 boyutunda bir 1B dizi ve üzerine yazılmadan önce dp[i-1][j-1] konumunda bulunan değeri saklamak için diagonal adlı bir değişken kullanabilirsiniz. Her satır için soldan sağa ilerleyin. Her hücreden sonra güncellenen dp[j] geçerli satırın değerini tutar; üzerine yazmadan önce önceki değeri diagonal içinde saklarsınız.
def lcs_o1_space(text1, text2):
m, n = len(text1), len(text2)
dp = [0] * (n + 1) # represents previous row
for i in range(1, m + 1):
diag = 0 # dp[i-1][j-1]
for j in range(1, n + 1):
temp = dp[j] # save current (will become diagonal for next j)
if text1[i-1] == text2[j-1]:
dp[j] = diag + 1
else:
dp[j] = max(dp[j], dp[j-1])
diag = temp
return dp[n]
print(lcs_o1_space('ABCBDAB', 'BDCABA')) # 4
print(lcs_o1_space('AGGTAB', 'GXTXAYB')) # 4LCS ile Düzenleme Mesafesi İlişkisi
LCS, Düzenleme Mesafesi (Levenshtein mesafesi) ile yakından ilişkilidir. LCS'yi biliyorsanız, yalnızca ekleme ve silme işlemlerini kullanarak minimum düzenleme mesafesini hesaplayabilirsiniz: edit_dist = m + n - 2 * LCS(s1, s2). s1 içindeki LCS'de bulunmayan her karakter için bir silme, s2 içindeki LCS'de bulunmayan her karakter için de bir ekleme gerekir. Burada yalnızca ekleme ve silmeye izin verdiğimiz için değiştirme sayılmaz; ancak bu formül, ilişkili problemlerde kullanışlıdır.
def lcs_length(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[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]
def min_edits_insert_delete(s1, s2):
lcs = lcs_length(s1, s2)
return len(s1) + len(s2) - 2 * lcs
print(min_edits_insert_delete('ABCD', 'ANCD')) # 2 (delete B, insert N)
print(min_edits_insert_delete('horse', 'ros')) # 5İki Dize İçin Silme İşlemi
İki Dize İçin Silme İşlemi (LeetCode 583), iki dizeyi eşit hâle getirmek için gereken minimum silme sayısını sorar. Koruduğunuz karakterler ortak bir alt dizi oluşturmalıdır; bu nedenle LCS'yi en büyük hâle getirip geri kalan her şeyi silmek istersiniz. Yanıt: m + n - 2 * LCS(s1, s2). Bu, yukarıdaki ekleme/silme düzenleme mesafesine denktir. Problemleri LCS açısından ifade etmek, güçlü bir indirgeme tekniğidir.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs = dp[m][n]
return m + n - 2 * lcs # deletions needed
print(min_distance('sea', 'eat')) # 2 (delete s, delete t)
print(min_distance('leetcode', 'etco')) # 4En Uzun Ortak Alt Dize
LCS (alt dizi) ile En Uzun Ortak Alt Dize kavramlarını karıştırmayın. Alt dize bitişik olduğundan, karakterler eşleşmediğinde komşuların maksimumunu almak yerine sayaç 0'a sıfırlanır. Bağıntı şu şekilde değişir: karakterler eşleşiyorsa dp[i][j] = dp[i-1][j-1] + 1; aksi hâlde dp[i][j] = 0. Tüm hücrelerde görülen en büyük değeri takip edin.
def longest_common_substring(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
max_len = 0
for i in range(1, m+1):
for j in range(1, n+1):
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
# else dp[i][j] stays 0 (reset)
return max_len
# LCS (subseq) vs substring:
print('LCS subseq:', lcs_length('ABCBDAB', 'BDCABA')) # 4 (BCBA)
print('LCS substring:', longest_common_substring('ABCBDAB', 'BDCABA')) # 2 (BD or AB)Dizi Karşılaştırma İçin LCS
LCS, dosyaları karşılaştırmak için fark araçlarında (Unix'teki diff gibi) yaygın olarak kullanılır. İki dosya arasındaki düzenleme betiği LCS'den türetilir: LCS'deki satırlar değiştirilmez, 1. dosyadaki fazladan satırlar silinir ve 2. dosyadaki fazladan satırlar eklenir. LCS'yi anlamak, sürüm denetimi sistemlerinin değişiklikleri nasıl takip ettiğini ve birleştirme çakışmalarının neden oluştuğunu kavramanıza yardımcı olur.
def diff(old_lines, new_lines):
'''Simple diff using LCS to find unchanged lines.'''
m, n = len(old_lines), len(new_lines)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if old_lines[i-1]==new_lines[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Backtrack to produce diff
output, i, j = [], m, n
while i>0 or j>0:
if i>0 and j>0 and old_lines[i-1]==new_lines[j-1]:
output.append(' '+old_lines[i-1]); i-=1; j-=1
elif j>0 and (i==0 or dp[i][j-1]>=dp[i-1][j]):
output.append('+ '+new_lines[j-1]); j-=1
else:
output.append('- '+old_lines[i-1]); i-=1
return list(reversed(output))
for line in diff(['a','b','c'], ['a','x','c']): print(line)En Kısa Ortak Üst Dizi
En Kısa Ortak Üst Dizi (LeetCode 1092), hem s1 hem de s2 dizisini alt dizi olarak içeren en kısa dizeyi ister. LCS'deki her karakter üst dizide bir kez yer alır; her iki dizedeki LCS dışı karakterlerin tümü de eklenmelidir. Uzunluk = m + n - LCS(s1, s2). Yeniden oluşturmak için aynı LCS geriye izleme yöntemini kullanın; eşleşmeyen konumlarda her iki dizeden gelen karakterleri de ekleyin.
def shortest_common_supersequence(s1, s2):
m, n = len(s1), len(s2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if s1[i-1]==s2[j-1]: dp[i][j]=dp[i-1][j-1]+1
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
# Reconstruct
result, i, j = [], m, n
while i>0 and j>0:
if s1[i-1]==s2[j-1]: result.append(s1[i-1]); i-=1; j-=1
elif dp[i-1][j]>dp[i][j-1]: result.append(s1[i-1]); i-=1
else: result.append(s2[j-1]); j-=1
while i>0: result.append(s1[i-1]); i-=1
while j>0: result.append(s2[j-1]); j-=1
return ''.join(reversed(result))
print(shortest_common_supersequence('abac', 'cab')) # 'cabac' length 5LCS Karmaşıklığı ve Mülakat İpuçları
Klasik LCS algoritması O(m×n) zamanda ve O(m×n) bellekte çalışır; kayan dizi tekniğiyle bellek kullanımı O(min(m,n)) değerine düşürülebilir. Önemli mülakat ipuçları: (1) Kodlamaya başlamadan önce DP durumunun neyi temsil ettiğini açıkça tanımlayın. (2) Eşleşme ve eşleşmeme durumlarını birbirinden ayrı ele alın. (3) Diziyi yeniden oluşturmanız istendiğinde, kodlamadan önce geriye izleme yöntemini açıklayın. (4) Sabır sıralamasıyla O(n log n) zamanda çözülebilen ilişkili 1B problem olarak En Uzun Artan Alt Dizi'nden (LIS) bahsedin.
# LCS: O(mn) time, O(min(m,n)) space with rolling array
# Longest Increasing Subsequence (related but 1D):
from bisect import bisect_left
def lis_length(nums):
'''Patience sorting: O(n log n) LIS length.'''
tails = []
for num in nums:
pos = bisect_left(tails, num)
if pos == len(tails): tails.append(num)
else: tails[pos] = num
return len(tails)
print(lis_length([10, 9, 2, 5, 3, 7, 101, 18])) # 4 (2,3,7,101 or 2,5,7,18)Hızlı Kontrol
Bu dersteki Veri Yapıları & Algoritmalar — Kodlama Mülakatı Hazırlığı kavramlarını ne kadar anladığınızı test edin.
Ders Özeti
Bu derste şunları öğrendiniz: LCS, eşleşme durumunda dp[i][j] = dp[i-1][j-1]+1, aksi hâlde max(dp[i-1][j], dp[i][j-1]) kullanır, gerçek dizi, eşleşmelerde çapraz ve eşleşmeme durumlarında daha büyük komşuya doğru geriye izlenerek yeniden oluşturulur ve LCS, düzenleme mesafesinin, silme işlemlerinin, en kısa ortak üst dizinin ve fark araçlarının temelini oluşturur. Sırada, LCS çerçevesine değiştirme işlemlerini ekleyen Düzenleme Mesafesi (Levenshtein) bağıntısını türeteceğiz.
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 dize için LCS bağıntısını tanımlayın, iki boyutlu tabloyu doldurun ve tabloda geriye doğru iz sürerek gerçek alt diziyi yeniden oluşturun. 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 2. 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
- Izgaralarda Benzersiz Yollar ve Minimum Yol Toplamı
- En Uzun Ortak Alt Dizi
- Düzenleme Uzaklığı (Levenshtein)
- İki Boyutlu DP için Alan Optimizasyonu