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)

Tested only

Time O(Σ L^2)Space 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.

Solution

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

90 saniyede hangi kalıp bunu ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?