Trie Data Structure Medium 0 attempts
GeeksforGeeks ↗

Trie Data Structure

Medium Tries GeeksforGeeks

Implement a Trie (prefix tree) with insert, search, and startsWith methods.

Example: insert("apple"), search("apple")→true, search("app")→false, startsWith("app")→true

Sample Input
—
Sample Output
—
Constraints
  • 1 <= word.length <= 2000
  • word consists of lowercase English letters
  • At most 3 * 10^4 calls
Topics
Tries

Trie with Object Nodes

class Trie {
  constructor() { this.root = {}; }
  insert(word) {
    let node = this.root;
    for (const c of word) { if (!node[c]) node[c] = {}; node = node[c]; }
    node.$ = true;
  }
  search(word) {
    let node = this.root;
    for (const c of word) { if (!node[c]) return false; node = node[c]; }
    return !!node.$;
  }
  startsWith(prefix) {
    let node = this.root;
    for (const c of prefix) { if (!node[c]) return false; node = node[c]; }
    return true;
  }
}

Time: O(L) per operation | Space: O(total characters)

Saved in this browser only. Private to you.

JavaScript