Medium

Implement Trie II (Prefix Tree)

LAB

Simulate insert, countWordsEqualTo, countWordsStartingWith, and erase. Return counts from the two count operations.

EXAMPLES

Example 1

Input
{
  "operations": [
    "insert",
    "insert",
    "countWordsEqualTo",
    "countWordsStartingWith",
    "erase",
    "countWordsEqualTo"
  ],
  "words": [
    "apple",
    "apple",
    "apple",
    "app",
    "apple",
    "apple"
  ]
}

Output
[
  2,
  2,
  1
]

FUNCTION SHAPE

operations: stringArraywords: stringArray→intArray

SOLUTION NOTE

This is the same idea. The only difference is we need to store a count variable representing how many words go through this node (how many words contain this node as a prefix) and word_count (how many words end at this node) at each node instead of just is_word.

It's interesting to note that for erase, ideally we can remove chars from the children map when count == 0 for proper memory management, but not strictly necessary for correctness. It would also be more robust, in the case we call erase(word) when word wasn't inserted. (in the constraints of this problem, we are guaranteed this won't happen, but useful to think about as a followup)

Reveal reference solution +

pythonREFERENCE

class Trie:
    def __init__(self):
        self.children = {}
        self.count = 0      # how many words go through this node
        self.word_count = 0 # how many words end at this node

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            if c not in node.children:
                node.children[c] = Trie()
            node = node.children[c]
            node.count += 1
        node.word_count += 1

    def countWordsEqualTo(self, word: str) -> int:
        node = self
        for c in word:
            if c not in node.children:
                return 0
            node = node.children[c]
        return node.word_count

    def countWordsStartingWith(self, prefix: str) -> int:
        node = self
        for c in prefix:
            if c not in node.children:
                return 0
            node = node.children[c]
        return node.count

    def erase(self, word: str) -> None:
        node = self
        for c in word:
            if c not in node.children:
                return
            node = node.children[c]
            node.count -= 1
        node.word_count -= 1

TimeO(len(word))

SpaceO(total characters)

Open on LeetCode ↗