Joker karakterli parantez dengesi

Problem

Yalnızca {, } ve * karakterlerinden oluşan bir string veriliyor. * bir joker: istersen {, istersen }, istersen boş string yerine sayılabilir. Jokerleri uygun seçtiğinde string dengeli bir süslü parantez dizisine dönüşebiliyorsa true, hiçbir seçimle dönüşemiyorsa false döndür. Dengeli demek: her { kendisinden sonra gelen bir } ile kapanıyor ve hiçbir önekte kapanan sayısı açılanı geçmiyor. Boş string dengelidir.

Bu, Goldman Sachs online assessment'ında bir adayın raporladığı biçim. LeetCode 678'deki problem birebir aynıdır; tek fark orada ( ve ) kullanılmasıdır. Parantez türü tek olduğu sürece karakterin kendisi önemli değil, aşağıdaki çözüm iki sürümü de çözer.

Girdi:  "{*}}"
Çıktı:  true         (* yerine { seçilirse "{{}}")

Girdi:  "*{"
Çıktı:  false        (son { hiçbir şekilde kapanamaz)

Girdi:  "{{*}*"
Çıktı:  true         (ilk * boş, ikinci * } seçilirse "{{}}")

Netleştirme soruları

• String'de bu üç karakter dışında karakter olabilir mi? (Olursa yok mu sayılmalı, hata mı?)
• Birden fazla parantez türü ({}, (), []) aynı anda olabilir mi? (Olursa problem değişir; aşağıya bak.)
• Boş string dengeli kabul ediliyor mu?
• String ne kadar uzun olabilir? (3^k deneme yapan brute force'un nerede çöktüğünü belirler.)
• Sadece evet/hayır mı isteniyor, yoksa jokerlerin nasıl atanacağı da mı?

İpuçları

Yaklaşım

Brute force: Her * için üç seçeneği ({, }, boş) dene, her tam atamayı klasik sayaç kontrolüyle doğrula. k joker için 3^k atama, her biri O(n): O(n · 3^k). Önek negatife düştüğünde dalı kesmek pratikte yardımcı olur ama en kötü durumu değiştirmez. Mülakatta başlangıç olarak söylenir, n = 100 bile bunu imkânsız kılar.

DP, ulaşılabilir denge kümesi: i karakter işlendikten sonra "açık parantez sayısı b olabilir mi?" sorusunu reachable[b] dizisinde tut. Başta yalnızca reachable[0] doğru. { her b'yi b+1'e, } her b > 0'ı b-1'e taşır; * üçünü birden yapar. Sonunda reachable[0] cevaptır. O(n²) zaman, O(n) bellek. LeetCode çözümlerinde görülen dp[i][j] aralık DP'si (i..j alt string'i dengeli mi) ise O(n³)'tür; bu problem için gereksiz pahalıdır.

Greedy, aralık: DP'deki kümeye dikkatle bakınca hep kesintisiz bir aralık olduğu görülür. { ve } aralığı bütünüyle kaydırır; * her değeri b-1, b, b+1'e yaydığı için aralık iki yana birer genişler ve içinde boşluk oluşmaz. Negatif değerleri atmak da aralığın alt ucunu kırpmaktan ibarettir. Bu yüzden kümenin tamamı yerine iki sayı yeter:

• minOpen: jokerler mümkün olduğunca kapatma (ya da boş) seçilirse açık sayısı,
• maxOpen: jokerler mümkün olduğunca açma seçilirse açık sayısı.

Kurallar: { ikisini de artırır, } ikisini de azaltır, * minOpen'ı azaltıp maxOpen'ı artırır. maxOpen < 0 ise hemen false: hiçbir atamada önek negatif olmaktan kurtulamaz. minOpen negatife düşerse sıfıra çekilir, çünkü negatif açık sayısı geçerli bir durum değildir; o jokerler kapatma yerine boş sayılır. Sonunda minOpen == 0 ise sıfır açıkla bitiren bir atama vardır. O(n) zaman, O(1) bellek.

Bu greedy, DP'nin durum sıkıştırılmış hâlidir; desen alanında "Dinamik programlama" yazmasının nedeni bu. Mülakatta greedy'yi doğrudan söyleyen adaydan "neden aralık?" sorusunun cevabı beklenir; cevap yukarıdaki kesintisizlik gözlemidir.

Alternatif, iki stack: Açılan parantezlerin ve jokerlerin index'lerini ayrı iki stack'te tut. } gelince önce açılan stack'inden, yoksa joker stack'inden eşle. Sonda kalan her açılan parantez için, kendisinden sonra gelen bir joker gerekir (index karşılaştırması). O(n) zaman, O(n) bellek. Atamayı da üretmek gerekiyorsa en okunaklı yol budur.

Birden fazla parantez türü olursa: {, (, [ ve her birinin yerine geçebilen joker birlikte olursa aralık hilesi çalışmaz; çünkü artık sadece sayı değil, açık parantezlerin sırası önemlidir. O sürüm Valid Parentheses'taki stack ile jokerleri birleştiren daha pahalı bir aramadır. Mülakatçı bunu takip sorusu olarak sorabilir.

Java çözümü

public final class ValidParenthesisString {

    // LeetCode 678 sürümü: '(' , ')' ve '*'
    public boolean checkValidString(String s) {
        return isBalanced(s, '(', ')');
    }

    // Greedy: açık parantez sayısının alabileceği değerler hep bir aralıktır [minOpen, maxOpen].
    // O(n) zaman, O(1) ek bellek. Aday raporundaki sürüm: isBalanced(s, '{', '}').
    public boolean isBalanced(String s, char open, char close) {
        int minOpen = 0;                                           // '*' mümkün olduğunca kapatıyorsa
        int maxOpen = 0;                                           // '*' mümkün olduğunca açıyorsa
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == open) {
                minOpen++;
                maxOpen++;
            } else if (c == close) {
                minOpen--;
                maxOpen--;
            } else if (c == '*') {
                minOpen--;                                         // '*' kapatma olabilir
                maxOpen++;                                         // ya da açma
            } else {
                throw new IllegalArgumentException("Beklenmeyen karakter: " + c);
            }
            if (maxOpen < 0) {
                return false;                                      // en iyimser senaryoda bile fazla kapatma var
            }
            minOpen = Math.max(minOpen, 0);                        // negatif açık sayısı geçerli bir durum değil
        }
        return minOpen == 0;                                       // 0 açıkla bitirmek mümkün mü?
    }

    // DP: i karakterden sonra ulaşılabilen açık sayılarının kümesi. O(n^2) zaman, O(n) bellek.
    public boolean isBalancedDp(String s, char open, char close) {
        int n = s.length();
        boolean[] reachable = new boolean[n + 2];
        reachable[0] = true;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c != open && c != close && c != '*') {
                throw new IllegalArgumentException("Beklenmeyen karakter: " + c);
            }
            boolean[] next = new boolean[n + 2];
            for (int balance = 0; balance <= i; balance++) {
                if (!reachable[balance]) {
                    continue;
                }
                if (c == open || c == '*') {
                    next[balance + 1] = true;
                }
                if ((c == close || c == '*') && balance > 0) {
                    next[balance - 1] = true;
                }
                if (c == '*') {
                    next[balance] = true;                          // '*' boş string
                }
            }
            reachable = next;
        }
        return reachable[0];
    }
}

Açma ve kapama karakterleri parametre olduğu için aynı kod hem aday raporundaki {/} sürümünü hem LeetCode'un (/) sürümünü çözer. Üç karakter dışında bir karakter geldiğinde sessizce yok saymak yerine IllegalArgumentException atılıyor; netleştirme sorusunun cevabına göre değiştirilebilir.

Karmaşıklık

k: joker sayısı.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı. 20.000 rastgele string (0-12 karakter, (, ), *) için greedy, DP ve 3^k brute force aynı sonucu verdi; her string ayrıca {/} karakterlerine çevrilip isBalanced(s, '{', '}') ile de doğrulandı. 1.000.000 karakterlik girdiler greedy ile anında çözüldü.

En sık yapılan hata minOpen'ı negatife düşmeye bırakmak: "(*)*" gibi girdilerde fazladan "kapatma" sayılır ve doğru cevap false'a döner. İkinci sık hata, maxOpen < 0 kontrolünü atlamak: minOpen her adımda sıfıra çekildiği için ")" ya da "())" gibi girdiler sonunda minOpen == 0 görünür ve yanlışlıkla true döner. Önek bir kez çöktüyse sonradan gelen karakterler onu kurtaramaz; bu yüzden kontrol her adımda yapılır.

Mülakatçı için

Online assessment'ta geldiyse süre baskısı altında greedy'yi bulmak beklenir; canlı görüşmede ise asıl ölçülen, adayın tek sayaçlı klasik çözümden "küme" fikrine nasıl geçtiği. Brute force'u söyleyip karmaşıklığını hesaplayan, sonra DP ile kümeyi tutan ve kümenin aralık olduğunu fark edip O(1) belleğe inen aday, problemin tamamını gerekçesiyle çözmüş olur. Greedy'yi ezberden yazan adaya "neden iki sayı yetiyor?" diye sormak ezberle anlamayı ayırır.

İpucu zamanlaması: Aday brute force'ta takılırsa birinci ipucuyla "joker olmasaydı?" sorusunu sor. DP'ye geldiyse ve O(n²)'de kalırsa küçük bir örnekte kümeyi yazdırıp "boşluk görüyor musun?" diye sor.

Takip soruları:

1. Sadece evet/hayır değil, jokerlerin geçerli bir atamasını da döndür. (Beklenen: iki stack ile index eşleme; kalan açıklar sonraki jokerlerle kapatılır, kullanılmayan jokerler boş olur.)
2. Üç parantez türü ve hepsinin yerine geçebilen joker olursa? (Beklenen: aralık fikri bozulur, sıra önemli hale gelir; stack durumlu arama ya da DP ve daha yüksek maliyet.)
3. String bir stream olarak, karakter karakter geliyor; her an "şu ana kadarki önek hâlâ geçerli bir dizinin başı olabilir mi?" sorusunu cevapla. (Beklenen: aynı minOpen/maxOpen; maxOpen >= 0 olduğu sürece evet.)

Benzer problemler

• Valid Parentheses (LeetCode 20) (bu sette: valid-parentheses).
• Minimum Remove to Make Valid Parentheses (LeetCode 1249) (bu sette: minimum-remove-to-make-valid-parentheses).
• Minimum Add to Make Parentheses Valid (LeetCode 921): tek sayaçlı greedy.
• Longest Valid Parentheses (LeetCode 32): stack ya da DP.
• Generate Parentheses (LeetCode 22): aynı önek kuralıyla backtracking.