Özet - LCS
- Algoritmalar kursu
- İleri seviye
- Ders 12/56
- 4 dk
İki dize için LCS uzunluğunu yazdıran mini görev yaparsın.
Özet - LCS
LCS; iki boyutlu DP tablosu ve geri izlemeyle iki dizinin ortak en uzun alt dizisini bulur. DNA hizalama ve diff araçlarında kullanılır.
Bu mini görevde iki dize için LCS uzunluğunu yazdıracaksın; tüm adımları birleştir.
LCS, Θ(mn) zaman ve bellek verir; klasik DP problemlerinden biridir.
Uygulama LCS yazdır
lcs_print(s1, s2) yaz. LCS uzunluğunu print() ile yazdır. lcs_print("AGGTAB", "GXTXAYB") çıktısı: 4.
Başlangıç kodu
def lcs_print(s1, s2):
# LCS yazdırÖrnek çözüm
def lcs_print(s1, s2):
# LCS yazdır
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])
print(dp[m][n])
lcs_print("AGGTAB", "GXTXAYB")Beklenen çıktı
4
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Özet - LCS: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
LCS |
Ortak alt dizi |
DP |
Tablo |
backtrack |
Geri iz |
O(mn) |
Doğrusal |
2 Tablo boyutu
Soru
dp = [[0] * (n + 1) for _ in range(____ + 1)
Cevap
dp = [[0] * (n + 1) for _ in range(m + 1)Açıklama: m doğru.
3 LCS zaman karmaşıklığı nedir?
- O(mn) Doğru cevap
- O(n^2)
- O(m^2)
- O(m + n)
Açıklama: O(mn).