Skip to content
Onsite
1 / 4

Implement Trie (Prefix Tree)

MediumP2Coding

Implement a trie (prefix tree) for lower-case words.

  • Trie() creates an empty trie.
  • insert(word) adds word to the trie.
  • search(word) returns true if exactly word was inserted earlier.
  • startsWith(prefix) returns true if some inserted word begins with prefix.

Example 1

Input
["Trie","insert","search","search","startsWith","insert","search"] [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
Output
[null,null,true,false,true,null,true]

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • Words consist of lower-case English letters
  • At most 3 * 10^4 calls in total

Hints

Run checks the 2 visible tests, Submit all 6.