Kelimelere bölme

Problem

Bir s string'i ve kelimelerden oluşan bir sözlük veriliyor. s, sözlükteki kelimelerin (her biri istendiği kadar tekrar kullanılabilir) arka arkaya eklenmesiyle tamamen oluşturulabiliyor mu? Boşluk yok; bölme noktalarını sen bulacaksın.

s = "yesilelma", sözlük = ["yesil", "elma"]      -> true   ("yesil" + "elma")
s = "elmaelma",  sözlük = ["elma"]               -> true   (kelime tekrar kullanılabilir)
s = "abcd",      sözlük = ["a", "abc", "b", "cd"] -> true  ("a" + "b" + "cd")

Son örnekte en uzun eşleşeni almak (abc) çıkmaz sokağa götürür (geriye d kalır); doğru bölme a + b + cd.

Netleştirme soruları

• Kelimeler tekrar kullanılabilir mi? (Evet.)
• Boş string true mu? (Evet; sıfır kelimeyle oluşur.)
• s'in ve sözlüğün boyutu, en uzun kelimenin uzunluğu ne? (Karmaşıklık analizi için.)
• Bölmenin kendisi mi, sadece evet/hayır mı isteniyor? (Tüm bölmeler istenirse problem Word Break II olur ve çıktı üstel büyüyebilir.)
• Büyük/küçük harf duyarlı mı?

İpuçları

Yaklaşım

Naif özyineleme / backtracking: Her önek denemesi için kalan soneki özyinelemeli çöz. Başarısız sonekler tekrar tekrar denenir; "aaaa...ab" ve ["a", "aa", "aaa", "aaaa"] gibi bir girdide üstel zamana gider (her bölme kombinasyonu denenir ve sonunda b yüzünden hepsi başarısız olur). Bu, sorunun bilinçli tuzağıdır.

Memoization: Özyinelemeyi start indeksine göre önbelleğe al; her start için cevap bir kez hesaplanır. O(n²) alt string kontrolü.

Tabulation (seçilen çözüm): canBuild[i] önekler üzerinden tanımlanır. Her end için, son kelimenin s[start, end) olduğunu varsay ve canBuild[start] doğruysa bu kelimeyi sözlükte ara. Bir start bulmak yeterlidir (break).

İyileştirme: Son kelime en fazla maxLen uzunluğunda olabilir, bu yüzden start sadece end - maxLen'e kadar geri gider. Sözlükte kısa kelimeler ve uzun bir s varsa bu fark büyüktür.

Alternatif: Sözlüğü bir trie'ye koyup her start'tan ileri doğru trie'de yürümek. Alt string oluşturma ve hash maliyetini kaldırır; sözlük büyük ve önek paylaşımı yüksekse faydalıdır.

Java çözümü

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public final class WordBreak {

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        int maxLen = 0;
        for (String w : wordDict) maxLen = Math.max(maxLen, w.length());

        boolean[] canBuild = new boolean[s.length() + 1]; // canBuild[i]: s[0, i) sözlükle bölünebilir mi
        canBuild[0] = true;                               // boş ön ek
        for (int end = 1; end <= s.length(); end++) {
            // son kelime s[start, end): sadece en fazla maxLen geriye bak
            for (int start = end - 1; start >= Math.max(0, end - maxLen); start--) {
                if (canBuild[start] && words.contains(s.substring(start, end))) {
                    canBuild[end] = true;
                    break;
                }
            }
        }
        return canBuild[s.length()];
    }
}

List<String> olarak gelen sözlük, aramaların O(1) ortalama olması için HashSet'e çevrilir; List.contains O(sözlük boyutu) olurdu. Java'da substring her çağrıda yeni bir string kopyalar (Java 7u6'dan beri paylaşımlı dizi yoktur); bu yüzden alt string maliyeti karmaşıklığa dahil edilmelidir.

Karmaşıklık

• Zaman: O(n · m · m); n = s.length(), m = maxLen. Her end için en fazla m start, her biri için O(m) alt string oluşturma ve hash. maxLen kısıtı olmadan O(n³).
• Bellek: O(n) DP dizisi + O(sözlükteki toplam karakter) hash set.

Kenar durumlar ve testler

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

• yesilelma: true; elmaelma (kelime tekrarı): true.
• kitaplik ve ["kitap", "lik2", "li"]: false.
• abcd ve ["a", "abc", "b", "cd"]: true (en uzun eşleşme açgözlülüğü başarısız).
• Boş string: true.
• "aaaa...ab" (36 a + b) ve ["a", "aa", "aaa", "aaaa"]: false, anında. Memoization'sız özyineleme bu girdide pratikte bitmez.
• 3.000 rastgele girdi (alfabe a-b, uzunluk 0-11) memoization'sız özyinelemeli referansla karşılaştırıldı (küçük girdilerde referans hızlıdır).

Mülakatçı için

Word Break, adayın "backtracking'de tekrar eden alt problemleri" fark edip memoization'a geçip geçmediğini ölçmek için idealdir. Çoğu aday doğal özyinelemeyle başlar; bu iyi bir başlangıçtır. Sonra kötü girdiyi (aaa...ab) ver ve karmaşıklığı sor. Güçlü aday memoization anahtarının sadece start indeksi olduğunu fark eder.

İpucu zamanlaması: Aday açgözlüyle başlarsa abcd örneğiyle dry run iste. Özyinelemeyi yazıp memoization eklemezse ikinci ipucunu (kötü girdi) ver. Tabulation'a geçmesi şart değildir; memoization'lı özyineleme de tam puan alır, ama s uzunluğu büyükse özyineleme derinliği sorulmalıdır.

Takip sorusu 1: Tüm geçerli bölmeleri döndür. Beklenen: memoization'lı DFS ile start -> List<String>; çıktının kendisi üstel olabileceği için en kötü durumda üstel zaman kaçınılmazdır; önce canBuild ile imkansız dalları budamak (LeetCode 140).

Takip sorusu 2: Bölme mümkünse en az kelimeli bölmeyi döndür. Beklenen: boolean yerine int minWords[i], geçişte minimum; Coin Change ile aynı yapı.

Takip sorusu 3: Bu algoritma gerçek bir üründe nerede kullanılır? Beklenen: Boşluksuz yazılan dillerde (Çince, Japonca) ya da URL/hashtag'lerde (#yesilelma) kelime bölütleme; gerçek sistemlerde her kelimeye olasılık verilip en olası bölme (Viterbi benzeri DP) seçilir.

Benzer problemler

• Word Break II (LeetCode 140)
• Concatenated Words (LeetCode 472)
• Coin Change (LeetCode 322)
• Decode Ways (LeetCode 91)
• Implement Trie (Prefix Tree) (LeetCode 208)