Kalıp #18

Trie

Önerilen

Sözlükler, kelime arama ve paylaşılan önekler için önek ağaçları.

Ne zaman kullanılır

Birçok string önek paylaşıyor veya startsWith / otomatik tamamlama / sözlük üzerinde tahta kelime araması lazım.

Tanıma ipuçları

Trie uygula / kelime ekle ve ara
Word Search II
Kelimeleri değiştir / sözlükte en uzun kelime

Yaygın tuzaklar

Kelime sonu işaretini salt önekten ayırmamak
Düğüm paylaşmamak (bellek şişmesi)
Kelime aramada tahtayı geri yüklemeden mutasyon

90 saniyelik tanıma egzersizi

Hangisi en iyi uyuyor?

Trie uygula / kelime ekle ve ara
Word Search II
Kelimeleri değiştir / sözlükte en uzun kelime

Ağaç DFSİkili AramaTrieGraf DFS

Interactive

Zihinsel model

Değişmezin tam adım adım anlatımı. Duraklat, noktalara tıkla veya ← → kullan. Her adımı kendi cümlelerinle anlatmayı hedefle.

Adım 1 / 8

Empty trie. Insert app, apple, bat.

Nasıl düşünülür

Her kenar bir karakter; kökten yol bir önek. Düğümler çocuk map’i (veya 26’lık dizi) ve isWord bayrağı tutar. Insert kenarları yürür/oluşturur; search isWord ister; startsWith yalnızca yolun varlığını ister.

Şablon şekilleri

Şekil	Temel hamle	Notlar
Map çocuklar	Esnek alfabe	Basit kod
Array[26]	Yalnızca küçük harf	Daha hızlı sabitler
Tahta DFS + trie	Ölü önekleri buda	Word Search II

Karmaşıklık temeli

Insert/search kelime uzunluğunda O(L). Alan insertler boyunca O(toplam karakter).

Şablondan probleme

Düğümü tanımla: children + isWord.
insert: yürü/oluştur; sonu işaretle.
search / startsWith: yürü; isWord farkı.
Çok kelimeli ızgara araması: trie yolu yaşarken DFS.

Şablon

TypeScript, Python ve C#’te aynı iskelet. Değişmezi uyarla; yapıyı koru.

Trie · Şablon

/** Trie template: insert / search / startsWith. */
export class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}
export class Trie {
  root = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isWord = true;
  }
  search(word: string): boolean {
    const node = this.walk(word);
    return Boolean(node?.isWord);
  }
  startsWith(prefix: string): boolean {
    return this.walk(prefix) != null;
  }
  private walk(s: string): TrieNode | null {
    let node: TrieNode | null = this.root;
    for (const ch of s) {
      if (!node!.children.has(ch)) return null;
      node = node!.children.get(ch)!;
    }
    return node;
  }
}

/** Trie template: insert / search / startsWith. */
export class TrieNode {
  children = new Map<string, TrieNode>();
  isWord = false;
}
export class Trie {
  root = new TrieNode();
  insert(word: string): void {
    let node = this.root;
    for (const ch of word) {
      if (!node.children.has(ch)) node.children.set(ch, new TrieNode());
      node = node.children.get(ch)!;
    }
    node.isWord = true;
  }
  search(word: string): boolean {
    const node = this.walk(word);
    return Boolean(node?.isWord);
  }
  startsWith(prefix: string): boolean {
    return this.walk(prefix) != null;
  }
  private walk(s: string): TrieNode | null {
    let node: TrieNode | null = this.root;
    for (const ch of s) {
      if (!node!.children.has(ch)) return null;
      node = node!.children.get(ch)!;
    }
    return node;
  }
}

Yol

Yola başla Problem tarayıcısında gör →

#ProblemTürZorlukBitti

1#208 Implement Trie (Prefix Tree)Rehbermedium
2#211 Design Add and Search Words Data StructureRehbermedium
3#212 Word Search IIRehberhard
4#421 Maximum XOR of Two Numbers in an ArrayRehbermedium
5#648 Replace WordsRehbermedium
6#720 Longest Word in DictionaryRehbermedium