Implement Trie (Prefix Tree) Python Solution

lcpy gen -n 208   # by problem number
lcpy gen -s implement_trie_prefix_tree   # by problem name

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

trie = Trie()
trie.insert("apple")
trie.search("apple")    # return True
trie.search("app")      # return False
trie.starts_with("app") # return True
trie.insert("app")
trie.search("app")      # return True

from leetcode_py.data_structures import DictTree, RecursiveDict


class Trie(DictTree[str]):
    END_OF_WORD = "#"

    # Time: O(1)
    # Space: O(1)
    def __init__(self) -> None:
        self.root: RecursiveDict[str] = {}

    # Time: O(m) where m is word length
    # Space: O(m)
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node:
                node[char] = {}
            node = node[char]
        node[self.END_OF_WORD] = True

    # Time: O(m) where m is word length
    # Space: O(1)
    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.END_OF_WORD in node

    # Time: O(m) where m is prefix length
    # Space: O(1)
    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True