Implement Trie (Prefix Tree) Leetcode Problem 208 [Python Solution]

If you’re new to the world of data structures and algorithms, the concept of a Trie (pronounced “try”) or Prefix Tree may seem a bit perplexing.

However, fret not, as we’re here to guide you through this interesting data structure question.

In this post, we’ll delve into the LeetCode problem 208, “Implement Trie (Prefix Tree),” and provide you with a Python solution.

Problem Overview

A Trie, or Prefix Tree, is a specialized tree data structure designed for efficiently storing and retrieving keys (usually strings) in a dataset.

The primary application of this data structure lies in tasks like autocomplete and spell checking.

The key features of a Trie include:

Trie() – Initializes a Trie object.
insert(String word) – Inserts the string word into the Trie.
search(String word) – Returns True if the string word exists in the Trie, and False otherwise.
startsWith(String prefix) – Returns True if there is a previously inserted string that has the prefix prefix, and False otherwise.

Now, let’s see how to implement this Trie step by step.

Understanding Trie Constraints

Before we dive into the Python solution, let’s understand the constraints of the problem:

1 <= word.length, prefix.length <= 2000
word and prefix consist only of lowercase English letters.
At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.

Implement Trie LeetCode Problem Solution

1. Bruteforce Approach

Let’s begin with a brute-force approach to implementing the Trie.

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.end = False

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

    def insert(self, word: str) -> None:
        curr = self.root
        for c in word:
            i = ord(c) - ord("a")
            if curr.children[i] is None:
                curr.children[i] = TrieNode()
            curr = curr.children[i]
        curr.end = True

    def search(self, word: str) -> bool:
        curr = self.root
        for c in word:
            i = ord(c) - ord("a")
            if curr.children[i] is None:
                return False
            curr = curr.children[i]
        return curr.end

    def startsWith(self, prefix: str) -> bool:
        curr = self.root
        for c in prefix:
            i = ord(c) - ord("a")
            if curr.children[i] is None:
                return False
            curr = curr.children[i]
        return True

2. An Efficient Approach with Trie

This implementation leverages a Trie data structure to efficiently store words and prefixes.

Here’s how it works:

View on GitHub ➹

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

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

    def insert(self, word: str) -&gt; None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word: str) -&gt; bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def startsWith(self, prefix: str) -&gt; bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Time and Space Complexity

Now, let’s discuss the time and space complexity of our efficient approach with Trie:

Time Complexity:
insert: O(N), where N is the length of the word to be inserted.
search and startsWith: O(M), where M is the length of the word or prefix being searched.
Space Complexity: O(N * M), where N is the number of words inserted, and M is the average length of the words.

Reasoning Behind Our Approach

The Trie data structure is a powerful tool for managing and searching for words efficiently.

It allows us to navigate through words letter by letter, providing quick access to whether a word exists or if there are words starting with a specific prefix.

The tree-like structure of the Trie ensures that we avoid unnecessary comparisons and can quickly identify the presence or absence of words.

In our implementation, we use a TrieNode class to create a tree-like structure.

The insert method inserts words letter by letter, while search and startsWith methods help us determine if a word exists or if there are words with a specific prefix.

By efficiently organizing the data and leveraging the Trie data structure, we achieve optimal time complexity, making this solution ideal for tasks like autocomplete and spell checking.

Conclusion

In this blog post, we’ve explored the LeetCode problem 208, “Implement Trie (Prefix Tree),” and provided an efficient Python solution.

We’ve learned about the Trie data structure and how it can be used for storing and retrieving words, making it a valuable tool for various applications, including autocomplete and spell checking.

We hope this post has been helpful in understanding Tries and how to implement them.