Özet - LCS

İ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.

Örnek çözümü göster

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")

Kendini test et

Özet - LCS: kavramları eşleştir

LCS

Ortak alt dizi
DP

Tablo
backtrack

Geri iz
O(mn)

Doğrusal

Tablo boyutu

dp = [[0] * (n + 1) for _ in range(____ + 1)

Cevabı göster

dp = [[0] * (n + 1) for _ in range(m + 1)

LCS zaman karmaşıklığı nedir?
- O(mn)
- O(n^2)
- O(m^2)
- O(m + n)
Cevabı göster

O(mn) — O(mn).

Sıradaki ders: Knapsack problemi

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler