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

Replace Words

Problem (yeniden ifade)

Kök sözlüğü. Cümledeki her kelimeyi, önek olan en kısa kökle değiştir; yoksa kelimeyi tut.

Sezgi

Tüm kökleri uç işaretli bir trie’ye ekle. Her kelime için uç veya miss olana kadar yürü.

Yaklaşımlar

Trie ile en kısa kök

Doğrulanmadı

Zaman O(Σ L)Alan O(Σ L)

Fikir. trie kur; kelime için karakterleri yürü; uçta o ana kadarki yolu döndür.

Yürüyüş. dict=[cat,bat,rat], sentence=“the cattle was rattled by the battery” → “the cat was rat by the bat”.

Trade-off. Kökleri uzunluğa göre sıralayıp startsWith da çalışır ama trie toplam uzunlukta doğrusal.

Çözüm

class Node {
  children = new Map<string, Node>();
  end = false;
}

export function replaceWords(dictionary: string[], sentence: string): string {
  const root = new Node();
  for (const w of dictionary) {
    let n = root;
    for (const c of w) {
      if (!n.children.has(c)) n.children.set(c, new Node());
      n = n.children.get(c)!;
    }
    n.end = true;
  }
  const replace = (word: string): string => {
    let n = root;
    let path = "";
    for (const c of word) {
      if (!n.children.has(c)) return word;
      n = n.children.get(c)!;
      path += c;
      if (n.end) return path;
    }
    return word;
  };
  return sentence.split(" ").map(replace).join(" ");
}

class Node {
  children = new Map<string, Node>();
  end = false;
}

export function replaceWords(dictionary: string[], sentence: string): string {
  const root = new Node();
  for (const w of dictionary) {
    let n = root;
    for (const c of w) {
      if (!n.children.has(c)) n.children.set(c, new Node());
      n = n.children.get(c)!;
    }
    n.end = true;
  }
  const replace = (word: string): string => {
    let n = root;
    let path = "";
    for (const c of word) {
      if (!n.children.has(c)) return word;
      n = n.children.get(c)!;
      path += c;
      if (n.end) return path;
    }
    return word;
  };
  return sentence.split(" ").map(replace).join(" ");
}

Şablon bağlantısı

Trie önek eşleştirme.

Yansıma

Kökten yürü, ilk bitiş bayrağı en kısa kök. Bayrak yoksa kelimenin kendisi kalır.
cat ve c varken cattle neden c olur? Daha kısa kök önce biter.
Sözlük boşsa cümle aynı. Kök kelimeye eşitse kelime değişmez.