class Node:
    def __init__(self, val):
        self.val = val 
        self.children = {}
        self.isEnd = False
        
class Solution: 
    def suggestedProducts(self, products, searchWord):
        # build trie
        root = Node('*')
        for product in products:
            node = root
            for char in product:
                if char not in node.children:
                    node.children[char] = Node(char)
                node = node.children[char]
            node.isEnd = True
        
        # dfs on the trie
        def dfs(node, path, result):
            if node.isEnd:
                result.append(''.join(path))

            for child_node_char, child_node in node.children.items():
                path.append(child_node_char)
                dfs(child_node, path, result)
                path.pop()
        
        # auto complete search word
        result = []
        node = root
        search = []
        for char in searchWord:
            if char not in node.children:
                result.append([])
            else:
                node = node.children[char]
                search.append(char)
                auto_complete = []
                dfs(node, search, auto_complete)
                auto_complete.sort()
                temp = []
                for i in range(min(len(auto_complete), 3)):
                    temp.append(auto_complete[i])
                result.append(temp[:])
                auto_complete = []
        return result