Implement Trie (Prefix Tree) | LeetCode | InterviewBit | Solution Explained

LeetCode problem 208. Implement Trie (Prefix Tree) asks us to implement a Prefix Tree or a Trie. They are popularly used in the case of auto-completion. They can suggest what the next character(s) of a given prefix could be. In this writeup, I explain how we can use & implement Prefix Trees. Problem Link.

Only by typing in lee my browser predicted what all I could want to search. Let’s see how to implement it.

Structure of Prefix Tree

an example of prefix tree or trie

Logic Summary

Each prefix tree consists of Nodes. In my implementation, I have:

class Node:
    def __init__(self, c, end=False):
        self.c = c # current character
        self.child = {} # 'x': Node()
        self.end = end # is this character the last or not

Note how close search and startsWith are in their logic. The only line changes is the last return line.

class Trie:
    def __init__(self):
        self.root = Node('#')

    def insert(self, word: str) -> None:
        self.curr = self.root
        for c in word:
            if c not in self.curr.child: 
                self.curr.child[c] = Node(c)
            self.curr = self.curr.child[c]
        self.curr.end = True

    def search(self, word: str) -> bool:
        self.curr = self.root
        for c in word:
            if c in self.curr.child:
                self.curr = self.curr.child[c]
            else:
                return False
        
        return self.curr.end
        

    def startsWith(self, prefix: str) -> bool:
        self.curr = self.root
        for c in prefix:
            if c in self.curr.child:
                self.curr = self.curr.child[c]
            else:
                return False

        return True

# 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)

    Leave a Reply

    Your email address will not be published. Required fields are marked *