En uzun ortak alt dizi

Problem

İki string veriliyor. Her ikisinden de karakter silerek (kalanların sırasını bozmadan) elde edilebilen ortak alt dizilerin en uzununun uzunluğunu döndür. Karakterlerin yan yana olması gerekmez (bu, "ortak alt string" probleminden farkıdır).

a = "kalem", b = "kelime"
Ortak alt diziler: "klm", "kem", "km", "e", ...
En uzun: "klm" (k-a-L-e-M / k-e-L-i-M-e) ya da "kem"
Çıktı: 3

a = "abc", b = "xyz"   -> 0
a = "",    b = "abc"   -> 0

Netleştirme soruları

• Uzunluk mu, alt dizinin kendisi mi isteniyor?
• Büyük/küçük harf duyarlı mı? Karakter seti ne? (Sadece eşitlik karşılaştırması yapılacağı için önemsiz, ama Unicode'da charAt ile kod noktası farkı söylenebilir.)
• String uzunlukları ne kadar? (n·m tablo belleği: 10^4 x 10^4 int tablo 400 MB eder.)
• Ortak alt dizi mi, ortak alt string mi? (Alt dizi.)

İpuçları

Yaklaşım

Kaba çözüm: a'nın tüm 2ⁿ alt dizisini üretip her birinin b'nin alt dizisi olup olmadığını O(m)'de kontrol et: O(2ⁿ · m).

Özyineleme: f(i, j): eşitse 1 + f(i+1, j+1), değilse max(f(i+1, j), f(i, j+1)). Üsteldir ama (i, j) çiftleri sadece n·m tanedir; alt problemler tekrar eder. Testlerde küçük girdiler için referans olarak kullanıldı.

2B tabulation (seçilen çözüm): Rekürans neden doğru?

• Son karakterler eşitse (a[i-1] == b[j-1]), bu karakteri eşleştirmek hiçbir zaman kötü değildir: herhangi bir optimal çözüm, bu son karakterleri eşleştirecek şekilde değiştirilebilir. Cevap 1 + lcs[i-1][j-1].
• Eşit değilse ikisi aynı anda LCS'nin son elemanı olamaz; en az biri atılabilir. İki seçeneğin büyüğü alınır.

Her hücre sol, üst ve sol-üst komşusuna bağlıdır; satır satır doldurmak bu bağımlılıkları sağlar.

Bellek optimizasyonu: Her satır sadece bir öncekine bağlıdır; iki satır (ya da dikkatli bir diagonal değişkeniyle tek satır) yeterlidir: O(min(n, m)) bellek. Bedeli: alt dizinin kendisini geri kurmak artık mümkün değildir, çünkü tablo yok. Bu yüzden aşağıdaki çözüm tam tabloyu tutar; mülakatta önce bunu yazıp sonra optimizasyonu söylemek doğru sıradır.

Java çözümü

public final class LongestCommonSubsequence {

    public int longestCommonSubsequence(String a, String b) {
        int n = a.length(), m = b.length();
        // lcs[i][j]: a'nın ilk i ve b'nin ilk j karakteri için cevap; 0. satır/sütun boş string
        int[][] lcs = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;                 // ortak son karakteri al
                } else {
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]); // birinden son karakteri at
                }
            }
        }
        return lcs[n][m];
    }
}

Karmaşıklık

• Zaman: O(n · m).
• Bellek: O(n · m) tablo; satır optimizasyonuyla O(min(n, m)).

Kenar durumlar ve testler

Testler main içinde çalıştırıldı:

• kalem ve kelime: 3.
• Ortak karakter yok: 0.
• Boş string: 0.
• Aynı string'ler: uzunluğun kendisi (4).
• aaaa ve a: 1 (tekrar eden karakter birden fazla kez eşlenmiyor).
• 2.000 rastgele çift (alfabe a-c, uzunluk 0-8) memoization'sız özyinelemeli referansla karşılaştırıldı.

Mülakatçı için

LCS, iki boyutlu DP'nin temel sorusudur; edit distance, diff ve DNA hizalama gibi problemlerin atasıdır. Gözlemle: aday durumu iki indeksle tanımlayabiliyor mu? Eşit olmayan durumda neden lcs[i-1][j-1] değil de iki komşunun maksimumu alındığını açıklayabiliyor mu? (n+1) x (m+1) boyut seçimiyle sınır kontrollerini ortadan kaldırıyor mu?

İpucu zamanlaması: Aday 4-5 dakikada son karakter gözlemini yapamazsa ilk ipucunu ver. Tablo indekslerinde off-by-one hataları yaygındır; hemen düzeltme, küçük bir örnekle ("ab", "b") tabloyu elle doldurmasını iste.

Takip sorusu 1: LCS'nin kendisini döndür. Beklenen: lcs[n][m]'den geri yürü; karakterler eşitse ekle ve çapraz git, değilse büyük olan komşuya git; sonda ters çevir. O(n + m).

Takip sorusu 2: Bir string'i diğerine çevirmek için en az ekleme/silme/değiştirme sayısı (Edit Distance). Beklenen: aynı tablo yapısı; eşitlikte çapraz, değilse 1 + min(üç komşu); temel durumlar 0 değil i ve j (LeetCode 72).

Takip sorusu 3: git diff iki dosya arasındaki farkı nasıl bulur? Beklenen: satırlar üzerinde LCS benzeri bir problem; pratikte O((n+m)·D) çalışan Myers algoritması (D fark sayısı). Benzer dosyalarda O(n·m) tablodan çok daha hızlıdır. Bunu bilmek şart değil, ama LCS'yi gerçek bir araçla ilişkilendiren aday artı alır.

Benzer problemler

• Edit Distance (LeetCode 72)
• Delete Operation for Two Strings (LeetCode 583)
• Shortest Common Supersequence (LeetCode 1092)
• Longest Palindromic Subsequence (LeetCode 516)
• Uncrossed Lines (LeetCode 1035)