Developers

Implement Trie (Prefix Tree)

MediumTrieGrade CAlso known as LeetCode 208

Implement a class Trie with these methods. Trie() creates an empty structure. insert(word) stores the string word. search(word) returns true if word was inserted before, and false otherwise. startsWith(prefix) returns true if some inserted word starts with prefix, and false otherwise.

A word is a prefix of itself, so after insert("apple") the call startsWith("apple") is true.

Examples

Input Trie(), insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")
Output [null, null, true, false, true, null, true]
Input Trie(), search("a"), startsWith("a")
Output [null, false, false]
Nothing was inserted.
Input Trie(), insert("a"), insert("a"), search("a")
Output [null, null, null, true]
Inserting twice is fine.

Constraints

  • 1 <= word.length, prefix.length <= 100
  • word and prefix contain only lowercase English letters
  • At most 20,000 calls to insert, search and startsWith in total

Stuck? Take one hint at a time

Common mistakes
  • Forgetting the end flag, so that search("app") is true after only inserting "apple".
  • Treating a prefix as a stored word: search must check the end flag, startsWith must not.
  • Creating a new child for a letter without checking whether it already exists, which discards the words stored under it.
  • Searching by looping over all stored words, which defeats the point of the structure.
  • In the sorted list version, comparing with a prefix check on the word before the lower bound position instead of at it.
Questions an interviewer may ask next
  • Add a method that returns all the stored words with a given prefix (autocomplete). How does the trie make that easy?
  • Add delete(word). What must you do so that nodes no longer used are freed?
  • The alphabet is huge (Unicode). What replaces the array of 26 children? How does that change the memory use?
  • Store a count at each node, so that you can answer "how many stored words start with this prefix" in O(L).

How often this is reported

Commonly reported across 5 of 25 tracked companies
5/25

Grade C: Reported in one source, or backed mainly by volume of reports. This reflects what candidates report, not a guarantee of what any company will ask.