Geçerli parantezler

Problem

Sadece (, ), [, ], { ve } karakterlerinden oluşan bir string veriliyor. String'in dengeli olup olmadığını döndür. Dengeli olması için her açılan parantez aynı türden bir kapanışla kapanmalı, kapanışlar açılışların ters sırasıyla gelmeli (en son açılan ilk kapanır) ve hiçbir kapanışın karşılığı eksik olmamalı.

Girdi:  "{[()()]}"
Çıktı:  true

Girdi:  "([)]"
Çıktı:  false      (köşeli parantez, normal parantezden önce kapanmalıydı)

Netleştirme soruları

• String'de başka karakter olabilir mi (harf, boşluk)? Olursa yok sayılmalı mı?
• Boş string geçerli mi? (Evet, kabul edilir.)
• Uzunluk sınırı? (10⁴; özyineleme derinliği önemli olabilir.)
• Sadece geçerli/geçersiz mi, yoksa hatanın konumu da mı isteniyor? (Gerçek bir parser'da konum gerekir.)

İpuçları

Yaklaşım

Brute force: String'den "()", "[]", "{}" çiftlerini, değişiklik kalmayana kadar tekrar tekrar sil; sonunda boş kaldıysa geçerli. Her tur O(n) ve en kötü durumda O(n) tur gerekir: O(n²). Yanlış değil, ama yavaş; testlerde referans olarak bunu kullandım.

Sayaç neden yetmez? Tek tür parantez olsaydı bir sayaç (açılışta +1, kapanışta -1, hiç negatife düşmeyecek, sonda 0 olacak) yeterdi. Üç türde sayaçlar "([)]" gibi iç içe geçmiş ama ters sırada kapanan durumu yakalayamaz: her türün sayacı dengede görünür.

Optimal, stack: Soldan sağa git. Açılışta stack'e ekle. Kapanışta stack boşsa ya da tepedeki eşleşmiyorsa false. Sonda stack boşsa true.

Küçük ama güzel bir hile: açılış karakterini değil, beklenen kapanışı stack'e koymak. ( gelince ) push edilir; kapanış geldiğinde sadece pop() == c kontrolü yeterli olur, eşleşme tablosuna gerek kalmaz. Alternatif okunaklı yazım Map.of(')', '(', ']', '[', '}', '{') ile kapanıştan açılışa eşlemedir.

Tek uzunluklu string asla dengeli olamaz; başta false dönmek ucuz bir erken çıkıştır (zorunlu değil).

Java çözümü

import java.util.ArrayDeque;
import java.util.Deque;

public final class ValidParentheses {

    public boolean isValid(String s) {
        if (s.length() % 2 == 1) {
            return false;                                          // tek uzunluk asla dengeli olamaz
        }
        Deque<Character> expectedClosers = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            switch (c) {
                case '(' -> expectedClosers.push(')');             // açılışta beklenen kapanışı sakla
                case '[' -> expectedClosers.push(']');
                case '{' -> expectedClosers.push('}');
                default -> {
                    if (expectedClosers.isEmpty() || expectedClosers.pop() != c) {
                        return false;                              // fazla ya da yanlış türde kapanış
                    }
                }
            }
        }
        return expectedClosers.isEmpty();                          // kapanmamış açılış kalmamalı
    }
}

java.util.Stack yerine ArrayDeque kullandım: Stack, Vector'dan türer ve her metodu synchronized'dır; Javadoc da Deque önerir. switch ifadesindeki default dalı, problemin garantisi gereği yalnızca kapanış karakterleri için çalışır; başka karakterler gelebilseydi ayrıca ele alınmalıydı (ör. yok saymak).

Karmaşıklık

• Zaman: O(n); her karakter bir kez işlenir, push/pop O(1).
• Bellek: O(n); en kötü durumda ("((((((") tüm açılışlar stack'te durur. Character boxing'i önlemek için char[] ile elle stack de yazılabilir.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; ayrıca 5.000 rastgele string'de (6 parantez karakterinden 0-11 uzunluk) "çiftleri tekrar tekrar sil" brute force'u ile karşılaştırıldı.

Mülakatçı için

Genelde ısınma ya da daha büyük bir sorunun ilk adımıdır; 10 dakikada bitmeli. Sinyal üç hata durumunun eksiksiz ele alınması ve doğru veri yapısının (ArrayDeque) seçilmesidir. Java'da Stack kullanan adaya neden kullanmaması gerektiğini sormak, dil bilgisini ölçmenin kolay bir yoludur. Hızlı biten adayla takip sorularına geçmek daha çok bilgi verir.

İpucu zamanlaması: İpucu genelde gerekmez. Aday sayaçla başlarsa "([)]" örneğini ver. Kod sonunda stack.isEmpty() kontrolünü unutursa "((" ile yürütmesini iste.

Takip soruları:

1. Geçersizse ilk hatanın konumunu döndür. (Beklenen: stack'te karakter yerine index tut; boş stack'te kapanışın index'i, sonda kalan en alttaki açılışın index'i.)
2. Geçerli hale getirmek için en az kaç ekleme gerekir? (Beklenen: tek tür için sayaçla açık ve kapanmamış sayısı; LeetCode 921.)
3. Bu bir JSON validator'ın parçası olsaydı, string literal içindeki parantezler ne olur? (Beklenen: tırnak içi durumu ve kaçış karakterleri için küçük bir durum makinesi; gerçek hayatta Jackson gibi streaming parser.)

Benzer problemler

• Minimum Remove to Make Valid Parentheses (LeetCode 1249) (bu sette: minimum-remove-to-make-valid-parentheses).
• Minimum Add to Make Parentheses Valid (LeetCode 921).
• Longest Valid Parentheses (LeetCode 32).
• Generate Parentheses (LeetCode 22): backtracking.
• Decode String (LeetCode 394): iç içe yapı için stack.