LeetCode 208: Implement Trie (Prefix Tree) Solution in Python Explained

Problem Statement

In LeetCode 208: Implement Trie (Prefix Tree), you need to implement a Trie class with three methods:

• Trie(): Initializes the Trie object.
• void insert(String word): Inserts a word into the Trie.
• boolean search(String word): Returns true if the word is in the Trie, false otherwise.
• boolean startsWith(String prefix): Returns true if any word starts with the prefix, false otherwise.

A Trie stores strings character-by-character, with nodes representing prefixes and a marker for complete words. This differs from graph scheduling in LeetCode 207: Course Schedule, focusing instead on efficient string operations.

Constraints

• 1 ≤ word.length, prefix.length ≤ 2000.
• word and prefix contain only lowercase English letters.
• At most 3 * 10⁴ calls to insert, search, and startsWith combined.

Examples

Let’s see a sequence of operations:

Copy codeTrie trie = new Trie();
trie.insert("apple");        // Inserts "apple"
trie.search("apple");        // Returns true
trie.search("app");          // Returns false
trie.startsWith("app");      // Returns true
trie.insert("app");          // Inserts "app"
trie.search("app");          // Returns true

This shows inserting and querying words and prefixes in the Trie.

Understanding the Problem

How do we implement LeetCode 208: Implement Trie (Prefix Tree) in Python? A Trie is like a tree where each node branches based on characters, with a flag to mark complete words. For insert("apple"), we create nodes for a-p-p-l-e and mark the last node as a word. search("app") checks for the word flag, while startsWith("app") just checks the path. This isn’t a linked list reversal like LeetCode 206: Reverse Linked List; it’s about building a prefix tree. We’ll use: 1. Trie with Dictionary: O(m) time per operation, O(m) space—our best solution (m = word length). 2. Trie with Array: O(m) time per operation, O(26m) space—an alternative.

Let’s explore the best solution.

Best Solution: Trie with Dictionary Approach

Explanation

The Trie with Dictionary approach uses a nested dictionary structure:

• Each node is a dictionary mapping characters to child nodes.
• A special key (e.g., '#') marks the end of a word.
• insert: Traverse or create nodes for each character, mark the end.
• search: Traverse nodes, check for the end marker.
• startsWith: Traverse nodes, check if the prefix exists.

This runs in O(m) time per operation (m = string length) and O(m) space per word (dynamic allocation), making it efficient and Pythonic—our best solution.

For ["apple", "app"], it builds a compact tree and handles queries fast.

Step-by-Step Example

Example 1: Operations Sequence

Goal: Implement and test the Trie.

• Step 1: Trie()
• Root = {{, empty dictionary.
• Step 2: insert("apple")
• Root: {'a': {{{.
• {'a': {'p': {{{{.
• {'a': {'p': {'p': {{{{{.
• {'a': {'p': {'p': {'l': {{{{{{.
• {'a': {'p': {'p': {'l': {'e': {'#': True{{{{{{.
• Step 3: search("apple")
• Traverse: a → p → p → l → e, '#' exists, return true.
• Step 4: search("app")
• Traverse: a → p → p, no '#', return false.
• Step 5: startsWith("app")
• Traverse: a → p → p, path exists, return true.
• Step 6: insert("app")
• Traverse: a → p → p, add '#'.
• {'a': {'p': {'p': {'#': True, 'l': {'e': {'#': True{{{{{{.
• Step 7: search("app")
• Traverse: a → p → p, '#' exists, return true.

How the Code Works (Trie with Dictionary) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codeclass Trie:
    def __init__(self):
        # Line 1: Initialize root
        self.root = {{
        # Empty dict as root (e.g., {{)
        self.end = '#'
        # Marker for word end (e.g., '#')

    def insert(self, word: str) -> None:
        # Line 2: Start at root
        node = self.root
        # Current node (e.g., {{)

        # Line 3: Traverse or create path
        for char in word:
            # Iterate chars (e.g., 'a', 'p', 'p', 'l', 'e')
            node = node.setdefault(char, {{)
            # Get or create child node (e.g., {'a': {{{)

        # Line 4: Mark word end
        node[self.end] = True
        # Add end marker (e.g., {'#': True{)

    def search(self, word: str) -> bool:
        # Line 5: Start at root
        node = self.root
        # Current node (e.g., {{)

        # Line 6: Traverse path
        for char in word:
            # Check each char (e.g., 'a', 'p', 'p')
            if char not in node:
                # Char not found (e.g., 'z')
                return False
            node = node[char]
            # Move to child (e.g., {'p': {{{)

        # Line 7: Check word end
        return self.end in node
        # True if '#' exists (e.g., true for "apple")

    def startsWith(self, prefix: str) -> bool:
        # Line 8: Start at root
        node = self.root
        # Current node (e.g., {{)

        # Line 9: Traverse path
        for char in prefix:
            # Check each char (e.g., 'a', 'p')
            if char not in node:
                # Prefix not found (e.g., 'b')
                return False
            node = node[char]
            # Move to child (e.g., {'p': {{{)

        # Line 10: Prefix exists
        return True
        # True if path exists (e.g., true for "app")

This solution is concise and leverages Python’s dictionary flexibility.

Alternative: Trie with Array Approach

Explanation

The Trie with Array approach uses a fixed-size array per node:

• Each node has a 26-element array (for a-z) and a boolean is_end.
• Map characters to indices (ord(char) - ord('a')).
• Operations traverse or create nodes similarly, but with arrays.

It’s O(m) time per operation and O(26m) space per word (fixed size), offering a traditional Trie structure.

Step-by-Step Example

For insert("apple"):

• Root: [None]*26, set root[0] = new node (for ‘a’).
• Continue: a → p → p → l → e, set is_end = True at e.

How the Code Works (Array)

Copy codeclass TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

class TrieArray:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            idx = ord(char) - ord('a')
            if not node.children[idx]:
                node.children[idx] = TrieNode()
            node = node.children[idx]
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            idx = ord(char) - ord('a')
            if not node.children[idx]:
                return False
            node = node.children[idx]
        return node.is_end

    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            idx = ord(char) - ord('a')
            if not node.children[idx]:
                return False
            node = node.children[idx]
        return True

Complexity

• Trie with Dictionary:
• Time: O(m) per operation – traverse string.
• Space: O(m) per word – dynamic allocation.
• Trie with Array:
• Time: O(m) per operation – traverse string.
• Space: O(26m) per word – fixed array size.

Efficiency Notes

Trie with Dictionary is our best solution for its space efficiency and Pythonic simplicity. Trie with Array uses more memory but is closer to the classic Trie implementation.

Key Insights

• Trie: Prefix-based tree.
• Dictionary: Flexible branching.
• Array: Fixed branching.

Additional Example

For ["cat", "car"]:

• Dictionary: {'c': {'a': {'t': {'#': True{, 'r': {'#': True{{{{.
• Array: Similar structure with arrays.

Edge Cases

• Empty string: Handleable with slight tweak (not per constraints).
• Single char: Works fine.
• Long words: Both scale with length.

Final Thoughts

LeetCode 208: Implement Trie (Prefix Tree) in Python is a stellar intro to Tries. Trie with Dictionary shines with efficiency and clarity, while Trie with Array offers a traditional approach. Want more? Try LeetCode 211: Design Add and Search Words Data Structure or LeetCode 212: Word Search II. Test your skills—Solve LeetCode 208 on LeetCode with ["apple"] operations—grow that Trie today!