Trie (Prefix Tree)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """Insert word into trie - O(m)"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word):
        """Check if word exists - O(m)"""
        node = self._traverse(word)
        return node is not None and node.is_end
    
    def startsWith(self, prefix):
        """Check if any word has prefix - O(m)"""
        return self._traverse(prefix) is not None
    
    def _traverse(self, s):
        """Helper to traverse trie"""
        node = self.root
        for char in s:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

def find_words(board, words):
    """Find all words from dictionary in grid"""
    # Build trie from words
    trie = Trie()
    for word in words:
        trie.insert(word)
    
    rows, cols = len(board), len(board[0])
    result = set()
    
    def dfs(r, c, node, path):
        char = board[r][c]
        if char not in node.children:
            return
        
        node = node.children[char]
        path += char
        
        if node.is_end:
            result.add(path)
        
        board[r][c] = '#'  # Mark visited
        
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                dfs(nr, nc, node, path)
        
        board[r][c] = char  # Restore
    
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, trie.root, "")
    
    return list(result)

class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.root = TrieNode()
        self.current_input = ""
        
        for sentence, count in zip(sentences, times):
            self._insert(sentence, count)
    
    def _insert(self, sentence, count):
        node = self.root
        for char in sentence:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.count = getattr(node, 'count', 0) + count
    
    def input(self, c):
        if c == '#':
            self._insert(self.current_input, 1)
            self.current_input = ""
            return []
        
        self.current_input += c
        return self._search(self.current_input)
    
    def _search(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        
        # DFS to find all sentences with this prefix
        results = []
        self._dfs(node, prefix, results)
        
        # Sort by count (desc), then lexicographically
        results.sort(key=lambda x: (-x[1], x[0]))
        return [s for s, _ in results[:3]]
    
    def _dfs(self, node, path, results):
        if node.is_end:
            results.append((path, node.count))
        for char, child in node.children.items():
            self._dfs(child, path + char, results)