CodePark/ problems / Word Index with Prefix Lookups
START PRACTICINGPRACTICE
Coding problem · Data structures and algorithms › Tries (prefix trees)

Word Index with Prefix Lookups

easyabout 15 minutes in an interview

Build a class WordIndex that stores words and answers two kinds of question about them.

  • insert(word) adds word to the index. Inserting the same word again changes nothing.
  • search(word) returns true if exactly word was inserted before, and false otherwise.
  • startsWith(prefix) returns true if at least one inserted word begins with prefix, and false otherwise. A word counts as beginning with itself, so after inserting "card", startsWith("card") is true.

Constraints:

  • Every word and prefix is 1 to 30 lowercase English letters (a to z).
  • There can be up to 20,000 inserts and 20,000 calls to search and startsWith in total, in any order. Each call must stay fast, no matter how many words are stored.
  • A new index is empty. Every search and startsWith returns false until something is inserted.
Input: insert("card"), insert("care"), search("car"), startsWith("car"), insert("car"), search("car") Output: undefined, undefined, false, true, undefined, true"car" is only the start of other words until it is inserted itself.
Input: insert("go"), startsWith("gone"), search("g") Output: undefined, false, false