Skip to the code
cf.
+25 XP

#368 Prefix Store for Autocomplete

medium

A search box needs a small store of known words that can answer two questions quickly: is this exact word stored, and does any stored word start with what the user typed?

Write a class PrefixStore with:

  • constructor(): starts empty.
  • insert(word): stores word (a non-empty lowercase string). Returns nothing.
  • has(word): returns true if exactly word was inserted.
  • hasPrefix(prefix): returns true if some inserted word starts with prefix (a non-empty string).

Each example lists the calls in order, then each call's arguments. The first call creates the object with new PrefixStore(…); the output lists what each call returns (null for the constructor and for methods that return nothing).

Example 1

Input: ["PrefixStore","insert","has","has","hasPrefix","insert","has"]
[[],["modal"],["modal"],["mod"],["mod"],["mod"],["mod"]]
Output: [null,null,true,false,true,null,true]

mod is only a prefix of modal until it is inserted itself.

Example 2

Input: ["PrefixStore","insert","hasPrefix","hasPrefix"]
[[],["toast"],["toasts"],["t"]]
Output: [null,null,false,true]

toasts is longer than any stored word.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • At most 3 * 10^4 calls.
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).