Implement Trie II (Prefix Tree)

MediumTreestrie

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Implement a Trie that stores a **multiset** of words, so the same word can be inserted several times. - insert(word) adds one copy of word. - countWordsEqualTo(word) returns how many copies of word are stored. - countWordsStartingWith(prefix) returns how many stored copies (counting duplicates) start with prefix. - erase(word) removes one copy of word. It is only called when at least one copy is stored.

Examples

Input: ["Trie","insert","insert","insert","countWordsEqualTo","countWordsStartingWith","erase","countWordsEqualTo","countWordsStartingWith","erase","countWordsStartingWith","countWordsEqualTo"] [[],["pen"],["pen"],["pencil"],["pen"],["pe"],["pen"],["pen"],["penc"],["pen"],["pen"],["pen"]]
Output: [null,null,null,null,2,3,null,1,1,null,1,0]
Two copies of "pen" and one "pencil" give 3 words starting with "pe". Each erase removes one "pen"; at the end only "pencil" starts with "pen".
Input: ["Trie","countWordsStartingWith","insert","countWordsEqualTo","countWordsStartingWith","erase","countWordsStartingWith"] [[],["a"],["a"],["a"],["ab"],["a"],["a"]]
Output: [null,0,null,1,0,null,0]
The trie starts empty. After inserting and erasing "a" it is empty again.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • Words and prefixes consist of lowercase English letters
  • At most 3 * 10^4 calls in total
  • `erase` is only called on a word that is currently stored

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More trie problems