মূল কনটেন্টে যান
🌍
গ্লোবাল DSA
প্যাটার্ন•টপিক 10 · Greedy, Trie & Design

10.2 Trie (Prefix Tree)

চিনবেন কীভাবে
"common prefix", "word dictionary", "autocomplete/suggestions", repeated prefix queries over many words — a tree that walks down one character at a time
Demo · approach · কোড — আগে নিজে চেষ্টা, আটকালে খুলুন

Demo: Implement Trie — LC 208 (Medium — Amazon/Google High)

Statement (Demo): Implement a Trie class with insert(word), search(word) and startsWith(prefix). Example: insert("apple"), search("apple") → true, startsWith("app") → true | ⚡ at most 3×10⁴ calls

Approach: Each node is a plain object keyed by the next character, with an isEnd flag where a word ends. search and startsWith differ only in the final isEnd check.

class Trie {
  constructor() {
    this.root = {};
  }
  insert(word) {
    let node = this.root;
    for (const c of word) node = node[c] ??= {};
    node.isEnd = true;
  }
  search(word) {
    const node = this._walk(word);
    return !!node && node.isEnd === true;
  }
  startsWith(prefix) {
    return this._walk(prefix) !== null;
  }
  _walk(s) {
    let node = this.root;
    for (const c of s) {
      node = node[c];
      if (!node) return null;
    }
    return node;
  }
}

Complexity: Every operation O(L) (L = word length)

Demo · Implement Trieplan · দিন ১১০LC 208
নোট · ফাঁকা

প্রবলেম

  • Word Search IIplan · দিন ১১৩🔥 Must-doLC 212
    (Hard — Google High; put every word in a Trie, then one DFS over the grid — combines with 7.3)

    Statement: Given an m × n board and a list of words, return every word that can be built from sequentially adjacent cells.
    Example: board=[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words=["oath","pea","eat","rain"] → ["oath","eat"] | ⚡ words.length ≤ 3×10⁴

    নোট · ফাঁকা
  • Search Suggestions SystemLC 1268
    (autocomplete — Trie, or sort + binary search)

    Statement: Given products and a searchWord, after each typed character return up to three lexicographically smallest products that start with the typed prefix.
    Example: products=["mobile","mouse","moneypot","monitor"], searchWord="mou" → [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse"]] | ⚡ products.length ≤ 1000

    নোট · ফাঁকা