DSA & System Design

Implement a Trie (Prefix Tree)

MediumTries (Prefix Trees)

A trie (prefix tree) stores a set of strings so that both whole words and prefixes can be looked up quickly. Implement a class Trie with:

  • constructor(): creates an empty trie.
  • insert(word): adds word to the trie. Inserting the same word twice has no extra effect.
  • search(word): returns true if word was inserted earlier, and false otherwise. A word that is only the beginning of an inserted word does not count.
  • startsWith(prefix): returns true if at least one inserted word starts with prefix (a whole word counts as a prefix of itself), and false otherwise.

Each test creates a Trie, calls the methods in the order shown, and compares the return values of search and startsWith (insert returns nothing, shown as null, and isn't checked).

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • Words and prefixes contain lowercase English letters only.
  • At most 3 * 10^4 calls in total.

Examples

Example 1

Input: ["Trie","insert","search","search","startsWith","insert","search"]
       [[],["code"],["code"],["cod"],["cod"],["cod"],["cod"]]
Output: [null,null,true,false,true,null,true]

After inserting "code", the path c-o-d exists, so startsWith("cod") is true but search("cod") is false. Once "cod" is inserted too, search finds it.

Example 2

Input: ["Trie","insert","insert","search","startsWith","startsWith","search"]
       [[],["car"],["cart"],["ca"],["ca"],["cars"],["cart"]]
Output: [null,null,null,false,true,false,true]

"ca" is only a prefix. No stored word continues "car" with an s, so startsWith("cars") is false.

Example 3

Input: ["Trie","search","startsWith"]
       [[],["a"],["a"]]
Output: [null,false,false]

An empty trie contains no words and no prefixes.

Each test creates the class with the first operation, then calls the methods in order. Output lists what each call returns; null marks the constructor and methods that return nothing, and their return values aren't checked.

JavaScript you'll use: Classes for data structures Map and Set Strings and characters

class Trie {
  constructor() {
    
  }

  /**
   * @param {string} word
   * @return {void}
   */
  insert(word) {
    
  }

  /**
   * @param {string} word
   * @return {boolean}
   */
  search(word) {
    
  }

  /**
   * @param {string} prefix
   * @return {boolean}
   */
  startsWith(prefix) {
    
  }
}

Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.