How hard is LeetCode 1804. Implement Trie II (Prefix Tree)?

LeetCode 1804. Implement Trie II (Prefix Tree) is rated Medium on LeetCode.

What is the time complexity of LeetCode 1804. Implement Trie II (Prefix Tree)?

The Python solution on this page runs in O(n), where n is the length of the string.

What is the space complexity of LeetCode 1804. Implement Trie II (Prefix Tree)?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1804. Implement Trie II (Prefix Tree) cover?

LeetCode 1804. Implement Trie II (Prefix Tree) is tagged Design, Trie, Hash Table and String on LeetCode.

Is LeetCode 1804. Implement Trie II (Prefix Tree) a premium problem?

Yes. LeetCode 1804. Implement Trie II (Prefix Tree) is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Implement Trie II (Prefix Tree) — LeetCode 1804 Python Solution

MediumLeetCode PremiumDesignTrieHash TableString

Problem: #1804
Pattern: Trie
Reading time: 8 min
Source: leetcode.com

The problem

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Example

Input: ["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsStartingWith"]
Output: [null, null, null, 2, 2, null, 1, 1, null, 0]
Explanation: Trie trie = new Trie();

Python solution

Python

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.v = self.pv = 0

    def insert(self, word: str) -> None:
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
            node.pv += 1
        node.v += 1

    def countWordsEqualTo(self, word: str) -> int:
        node = self.search(word)
        return 0 if node is None else node.v

    def countWordsStartingWith(self, prefix: str) -> int:
        node = self.search(prefix)
        return 0 if node is None else node.pv

    def erase(self, word: str) -> None:
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            node = node.children[idx]
            node.pv -= 1
        node.v -= 1

    def search(self, word):
        node = self
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                return None
            node = node.children[idx]
        return node


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.countWordsEqualTo(word)
# param_3 = obj.countWordsStartingWith(prefix)
# obj.erase(word)

Complexity

Measure	Complexity
Time	O(n), where n is the length of the string
Space	O(n) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 1804. Implement Trie II (Prefix Tree) is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1804. Implement Trie II (Prefix Tree)?: LeetCode 1804. Implement Trie II (Prefix Tree) is rated Medium on LeetCode.
What is the time complexity of LeetCode 1804. Implement Trie II (Prefix Tree)?: The Python solution on this page runs in O(n), where n is the length of the string.
What is the space complexity of LeetCode 1804. Implement Trie II (Prefix Tree)?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1804. Implement Trie II (Prefix Tree) cover?: LeetCode 1804. Implement Trie II (Prefix Tree) is tagged Design, Trie, Hash Table and String on LeetCode.
Is LeetCode 1804. Implement Trie II (Prefix Tree) a premium problem?: Yes. LeetCode 1804. Implement Trie II (Prefix Tree) is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.