Joker karakterli kelime sözlüğü

Problem

Kelime ekleyip arayabileceğin bir sözlük sınıfı yaz:

• addWord(word): küçük harfli kelimeyi ekler.
• search(pattern): desen, eklenmiş bir kelimeyle tam olarak eşleşiyorsa true. Desende . karakteri herhangi tek bir harf yerine geçer.

addWord("kale"), addWord("kule"), addWord("kal")

search("k.le")   -> true    (kale ve kule)
search("kal")    -> true
search("ka")     -> false   (önek, kelime değil)
search("...")    -> true    (kal)
search(".....")  -> false   (5 harfli kelime yok)
search("...e")   -> true

Netleştirme soruları

• . tam olarak bir karakter mi, yoksa * gibi sıfır ya da daha fazla mı? (Tam bir.)
• Desende kaç . olabilir? (LeetCode'da en fazla 2; bu, en kötü durum analizini değiştirir.)
• Eşleşme tam kelime mi, önek mi? (Tam kelime.)
• addWord ve search oranı ne? Okuma ağırlıklı mı? (Yapı seçimini etkiler.)
• Kelime uzunluğu ve sayısı ne kadar?

İpuçları

Yaklaşım

Kaba çözüm: Kelimeleri bir listede tut; her aramada her kelimeyle karakter karakter karşılaştır (uzunluk farklıysa atla). O(N · L) arama. Bir iyileştirme: kelimeleri uzunluğa göre gruplayıp (Map<Integer, List<String>>) sadece aynı uzunluktakilerle karşılaştırmak. Bu, joker sayısı çoksa trie'den bile iyi olabilir.

Trie + DFS (seçilen çözüm): Kelimeler bir trie'de saklanır. Harfli karakterlerde tek bir yol izlenir; .'da o düğümün tüm çocukları denenir. Desende joker yoksa arama O(L)'dir. Her joker dallanmayı en fazla 26 katına çıkarır; ama trie'nin seyrekliği sayesinde pratikte sadece var olan çocuklar gezilir ve gezilen düğüm sayısı hiçbir zaman trie'nin toplam düğüm sayısını geçemez.

Erken çıkış önemlidir: bir dal eşleşme bulduğunda diğer dalları gezmeye gerek yoktur.

Java çözümü

public final class WordDictionary {

    private static final class Node {
        final Node[] children = new Node[26];
        boolean endOfWord;
    }

    private final Node root = new Node();

    public void addWord(String word) {
        Node node = root;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) node.children[idx] = new Node();
            node = node.children[idx];
        }
        node.endOfWord = true;
    }

    /** '.' herhangi bir harfle eşleşir. */
    public boolean search(String pattern) {
        return matches(root, pattern, 0);
    }

    private boolean matches(Node node, String pattern, int pos) {
        if (pos == pattern.length()) return node.endOfWord;
        char ch = pattern.charAt(pos);
        if (ch == '.') {
            for (Node child : node.children) {            // joker: tüm dalları dene
                if (child != null && matches(child, pattern, pos + 1)) return true;
            }
            return false;
        }
        Node child = node.children[ch - 'a'];
        return child != null && matches(child, pattern, pos + 1);
    }
}

for (Node child : node.children) dizideki null girişleri de gezer; null kontrolü bu yüzden gerekli. Seyrek bir trie'de çocukları Map olarak tutmak jokerde sadece var olan çocukları gezmeyi sağlar.

Karmaşıklık

• addWord: O(L) zaman.
• search: Jokersiz O(L). Joker varsa en kötü O(min(26^d · L, düğüm sayısı)) mertebesinde; d joker sayısıdır. Tamamen .'dan oluşan bir desen, o derinliğe kadar tüm trie'yi gezebilir.
• Bellek: O(T · 26) trie düğümleri (T toplam karakter); arama sırasında O(L) özyineleme derinliği.

Kenar durumlar ve testler

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

• k.le iki kelimeyle eşleşiyor; kal tam eşleşiyor; ka önek olduğu için false.
• ... (3 harfli kelime var): true; .....: false.
• k.lem: false; ...e: true.
• Boş sözlükte .: false.
• 50 tur × 300 rastgele işlem: her aramada . joker olarak java.util.regex.Pattern'e çevrildi ve eklenen kelimeler listesinde matches ile kontrol edildi. Regex referansı, sözlüğün sonucunu bağımsız bir yolla doğrular. (Desende sadece harf ve . olduğu için regex'e dönüşüm güvenli.)

Mülakatçı için

Bu soru trie bilgisini backtracking ile birleştirir. Gözlemle: aday jokeri tek bir yol gibi mi ele alıyor, yoksa dallanmayı fark ediyor mu? Özyinelemenin temel durumunu (desen sonu: endOfWord) doğru kuruyor mu, yoksa sadece "yol var mı" diye mi bakıyor? Erken çıkış yapıyor mu?

Karmaşıklık konuşması bu sorunun en zor kısmıdır; "jokersiz O(L), jokerli en kötü durumda üstel ama trie boyutuyla sınırlı" cevabı yeterlidir.

İpucu zamanlaması: Aday trie'yi kurduktan sonra jokerde takılırsa ikinci ipucunu ver. Özyineleme yerine iteratif (kuyrukta düğüm kümesi taşıyan) bir çözüm de doğrudur: her karakterde "şu an olabileceğim düğümler" kümesini ilerletir.

Takip sorusu 1: * jokeri de gelsin (sıfır ya da daha fazla herhangi karakter). Beklenen: *'da iki seçenek: *'ı atla (pos + 1, aynı düğüm) ya da bir karakter tüket (her çocuk, pos aynı). Tekrar eden (düğüm, pos) durumları için memoization gerekir; aksi halde üstel patlar.

Takip sorusu 2: Aynı yapı bir ızgaradaki kelimeleri bulmak için nasıl kullanılır? Beklenen: Word Search II (LeetCode 212); kelimeler trie'ye konur, ızgarada her hücreden DFS yapılırken trie'de eşzamanlı ilerlenir; bulunan kelimelerin dalları budanır.

Takip sorusu 3: Sözlük 1 milyon kelimelik ve servis saniyede binlerce arama alıyor, kelime ekleme nadir. Eşzamanlılığı nasıl yönetirsin? Beklenen: okuma ağırlıklı iş yükü için ReadWriteLock ya da copy-on-write (yeni trie'yi kurup referansı volatile/AtomicReference ile değiştirmek); okumaların kilitsiz olması.

Benzer problemler

• Implement Trie (Prefix Tree) (LeetCode 208)
• Word Search II (LeetCode 212)
• Wildcard Matching (LeetCode 44)
• Regular Expression Matching (LeetCode 10)
• Prefix and Suffix Search (LeetCode 745)