895. Prefix Tree

Medium3.5 points estimatedTrieDesignStringHash Table3 hints
RPby Rohit Parihar

A harbour office keeps a registry of vessel names typed one at a time, and clerks need instant look-ups. Build the class PrefixTree with an empty constructor.

  • insert(word) stores the lowercase word in the registry. Storing a name that is already present changes nothing.
  • search(word) returns true only if exactly this word was inserted before.
  • startsWith(prefix) returns true if at least one inserted word begins with prefix (a word counts as a prefix of itself).

Each call must cost time proportional to the length of its argument, not to the number of stored words.

Example 1

Input:
operations = ["PrefixTree","insert","search","startsWith","insert","search"]arguments = [[],["quartz"],["quart"],["quart"],["quart"],["quart"]]
Output:
[null,null,false,true,null,true]
Explanation:

Only quartz is stored at first, so quart is a prefix but not a stored word; after inserting it, it is found.

Example 2

Input:
operations = ["PrefixTree","insert","search","startsWith","startsWith"]arguments = [[],["nebula"],["nebulae"],["nebulae"],["n"]]
Output:
[null,null,false,false,true]
Explanation:

A longer string than any stored word is never found, while the single letter n starts nebula.

Constraints

1 ≤ word.length, prefix.length ≤ 50

All strings consist of lowercase English letters.

At most 2000 calls in total.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(L) per call
Space
O(total inserted characters)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.