LeetCode Solutions Blog

Implement Trie II (Prefix Tree)

Number: 1949

Difficulty: Medium

Paid? Yes

Companies: DoorDash

Problem Description

Design and implement a Trie (Prefix Tree) with insertion, counting of full words, counting of words with a given prefix, and erasing a word. The trie must support duplicate entries, meaning the same word can be inserted multiple times and erased incrementally.

Key Insights

Use a tree structure where each node corresponds to a character.
Each node stores the number of words that pass through it (prefix count) and the number of words that end at that node.
Insertion increments counts along the path.
Erasing decrements counts along the path and guarantees the word exists.
Counting functions simply read the stored counts at the appropriate nodes.

Space and Time Complexity

Time Complexity:
• Insert, countWordsEqualTo, countWordsStartingWith, and erase all operate in O(L) time, where L is the length of the word or prefix.

Space Complexity:
• In the worst-case, space complexity is O(N * L) for storing N words of maximum length L, though common prefixes reduce overall storage.

Solution

The solution involves building a Trie where each node maintains two pieces of data:

A mapping (or array) of child nodes for each character.
Two counters: one for the number of words that pass through the node (prefix count) and one for the number of words that end at that node (word count).

When inserting a word, traverse the Trie and update both counts. For counting words equal to a given word, traverse the Trie and return the word count at the terminal node. For counting words with a given prefix, traverse to the last character of the prefix and return its prefix count value. The erase operation decrements the counts along the path for the word, ensuring that duplicate insertions are handled correctly.

Code Solutions

# Python implementation of Trie II (Prefix Tree)

class TrieNode:
    def __init__(self):
        # Dictionary to store child nodes for each character
        self.children = {}
        # Counter for words that pass through this node (prefix count)
        self.countPrefix = 0
        # Counter for words ending at this node
        self.countWord = 0

class Trie:
    def __init__(self):
        # Initialize the root of the Trie
        self.root = TrieNode()

    def insert(self, word):
        # Start from the root
        current = self.root
        for ch in word:
            # If the character is not present, add a new TrieNode
            if ch not in current.children:
                current.children[ch] = TrieNode()
            # Move to the child node
            current = current.children[ch]
            # Increment prefix count for each node encountered
            current.countPrefix += 1
        # At the end of the word, increment count for words ending here
        current.countWord += 1

    def countWordsEqualTo(self, word):
        # Start from the root
        current = self.root
        for ch in word:
            if ch not in current.children:
                # If any character is missing, word does not exist
                return 0
            current = current.children[ch]
        # Return count of words ending at this node
        return current.countWord

    def countWordsStartingWith(self, prefix):
        # Start from the root
        current = self.root
        for ch in prefix:
            if ch not in current.children:
                # No string in trie starts with the given prefix
                return 0
            current = current.children[ch]
        # Return prefix count
        return current.countPrefix

    def erase(self, word):
        # Start from the root
        current = self.root
        for ch in word:
            # Move to the required child node and decrement prefix counter
            current = current.children[ch]
            current.countPrefix -= 1
        # Decrement the word frequency at the terminal node
        current.countWord -= 1

# Example usage:
# trie = Trie()
# trie.insert("apple")
# trie.insert("apple")
# print(trie.countWordsEqualTo("apple"))  # Output: 2
# print(trie.countWordsStartingWith("app"))  # Output: 2
# trie.erase("apple")
# print(trie.countWordsEqualTo("apple"))  # Output: 1
# print(trie.countWordsStartingWith("app"))  # Output: 1
# trie.erase("apple")
# print(trie.countWordsStartingWith("app"))  # Output: 0