Leetcode 208. Implement Trie (Prefix Tree)

Problem

Leetcode 208 - Implement Trie (Prefix Tree)

Example:

Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]

Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // return True
trie.search("app");     // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app");     // return Tru

Approach

We can use a node that has map to represent each letter and boolean that indicates the end of word.

For exmaple, our trie for ‘apple’ would be

at root {a}, in a: {p}, in p: {p} in p: {l} and so forth.

If we were to insert another word that starts with ‘a’, for example ‘appointment’,

at root {a}, in a: {p}, in p: {p}, in p: {l, o}, and so forth.

For search, we can search letter and each Nodes if it exists and if it’s end of word

Here is the Python code for the solution:

class TrieNode:
    def __init__(self):
        self.letterMap = {}
        self.endOfWord = False
    
class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        curr = self.root

        for ch in word:
            if ch not in curr.letterMap:
                curr.letterMap[ch] = TrieNode()
            curr = curr.letterMap[ch]
        curr.endOfWord = True
    
    def search(self, word: str) -> bool:
        curr = self.root

        for ch in word:
            if ch not in curr.letterMap:
                return False
            curr = curr.letterMap[ch]
        
        return curr.endOfWord
    
    def startsWith(self, prefix: str) -> bool:
        curr = self.root

        for ch in prefix:
            if ch not in curr.letterMap:
                return False
            curr = curr.letterMap[ch]
        
        return True  

Time Complexity and Space Complexity

Time Complexity: $O(n)$ for each function call

Space Complexity: $O(t)$ where t is the total number of TrieNodes created in Trie