MediumNo. 0208

Implement Trie (Prefix Tree) — LeetCode 208 Python Solution

Pattern
Trie
Topics
Design, Trie, Hash Table, String
Reading time
7 min

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", "search", "search", "startsWith", "insert", "search"]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();

Python solution

PythonSolution
class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

    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.is_end = True

    def search(self, word: str) -> bool:
        node = self._search_prefix(word)
        return node is not None and node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self._search_prefix(prefix)
        return node is not None

    def _search_prefix(self, prefix: str):
        node = self
        for c in prefix:
            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.search(word)
# param_3 = obj.startsWith(prefix)

Complexity

Time
O(n)
Space · auxiliary
O(q × m × |Σ|), where q is the number of inserted strings

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 208. Implement Trie (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.

Related problems

Related problems
No.ProblemDifficulty
0676Implement Magic DictionaryMedium
0677Map Sum PairsMedium
0745Prefix and Suffix SearchHard
2227Encrypt and Decrypt StringsHard
0139Word BreakMedium
0140Word Break IIHard

Frequently asked questions

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

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

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

The Python solution on this page runs in O(n).

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

The Python solution on this page uses O(q × m × |Σ|), where q is the number of inserted strings auxiliary space.

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

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

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.