Problem statement

https://binarysearch.com/problems/Search-Engine/

Solution

Equal to Leetcode 0211. Design Add and Search Words Data Structure.

Complexity

See complexity of Leetcode problem.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end_node = 0
        
class SearchEngine:
    def __init__(self):
        self.root = TrieNode()      

    def add(self, word):
        root = self.root
        for symbol in word:
            root = root.children.setdefault(symbol, TrieNode())
        root.end_node = 1
        
    def exists(self, word):
        def dfs(node, i):
            if i == len(word): return node.end_node
               
            if word[i] == ".":
                for child in node.children:
                    if dfs(node.children[child], i+1): return True
                    
            if word[i] in node.children:
                return dfs(node.children[word[i]], i+1)
            
            return False
    
        return bool(dfs(self.root, 0))