Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumtrie

Longest Word in Dictionary

Problem (yeniden ifade)

Kelime listesinden, listedeki diğer kelimelerden harf harf inşa edilebilen en uzun kelimeyi döndür. Beraberlikte sözlük sırasına göre en küçük. Yoksa boş.

Sezgi

Geçerli kelimenin her öz öneki de sözlükte vardır. Uzunluğa göre azalan, sonra sözlük sırasına göre sırala; ilk geçerliyi seç.

Yaklaşımlar

Küme ile önek zinciri (trie fikri)

Doğrulanmadı

Zaman O(Σ L^2)Alan O(Σ L)

Fikir. Kelimelerin hash kümesi; tüm önekleri kontrol et. Kökten, uç işaretli çocukları tercih eden trie DFS eşdeğerdir.

Adım adım. [“w”,“wo”,“wor”,“worl”,“world”] → “world”.

Trade-off’lar. Önek kümesi yeter; artımlı eklemede tam trie parlar.

Çözüm

export function longestWord(words: string[]): string {
  const set = new Set(words);
  words = [...words].sort((a, b) => b.length - a.length || (a < b ? -1 : a > b ? 1 : 0));
  for (const w of words) {
    let ok = true;
    for (let i = 1; i < w.length; i++) {
      if (!set.has(w.slice(0, i))) {
        ok = false;
        break;
      }
    }
    if (ok) return w;
  }
  return "";
}

export function longestWord(words: string[]): string {
  const set = new Set(words);
  words = [...words].sort((a, b) => b.length - a.length || (a < b ? -1 : a > b ? 1 : 0));
  for (const w of words) {
    let ok = true;
    for (let i = 1; i < w.length; i++) {
      if (!set.has(w.slice(0, i))) {
        ok = false;
        break;
      }
    }
    if (ok) return w;
  }
  return "";
}

Şablon bağlantısı

Trie / önek zinciri tamlığı.

Yansıma

Aday kelimenin her öneki de sözlükte. En uzun; eşit uzunlukta sözlük sırası küçük olan.
Set ile önek zinciri trie ile aynı soru. Öneki eksik uzun kelime elenir.
Tek harf her zaman aday. Boş sözlük boş dizgi.