208. Implement Trie (Prefix Tree) 🔥

Medium

Problem:

Implement the insert, search, and startWith methods of the Trie.

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 True

https://leetcode.com/problems/implement-trie-prefix-tree/

Solution:

• insert(): In a Trie, each character serves as a key for the child nodes, deepening progressively, and only becomes True when the word is fully formed.

• search(): Continue deep traversal character by character and, in the end, check if the word is True.

• startsWith(): Iterating over the string using a loop, keep descending through child nodes, only checking if the child node exists or not.

class TrieNode:
    def __init__(self):
        self.word = False
        self.children = collections.defaultdict(TrieNode)
class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            # if char not in node.children -> defaultdict
            node = node.children[char]
        node.word = True

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

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