“Not all roots are buried down in the ground, some are at the top of a tree.”
~ Jinvirle

Day 14 of the May LeetCoding Challenge by Leetcode

Problem definition: Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:

• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.

Sample Testcase

Testcase 1

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

I highly encourage you to attempt this problem on your own before looking at my solution.

Approach

Before coming to implementation, I suggest you read a bit about Prefix Trees. It will help you understand the solution better!

Solution

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root={}
        
    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        current=self.root
        for l in word:
            if l not in current:
                current[l]={}
            current=current[l]
        current['$']='$'
        
    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        current=self.root
        for l in word:
            if(l not in current):
                return False
            current=current[l]
        return '$' in current

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        current=self.root
        for l in prefix:
            if(l not in current):
                return False
            current=current[l]
        return True

Submission Details

Total test cases passed: 15 / 15
Runtime: 128 ms
Memory Usage: 27.2 MB

Note: This submission was better than 95.31% of Python3 solutions in terms of runtime! Try to come up with a better approach! 🌚

I would really recommend you to explore this side of the Computer Science and tune in to the journey of competitive programming to write better, cleaner, efficient and optimal code! 😀

If you have a better approach to this problem, or for any other queries feel free to reach out to me! 😇