Trie (Prefix Tree)

class TrieNode:
    def __init__(self):
        self.children = {}   # char -> TrieNode
        self.is_end = False  # True if a complete word ends here

class Trie:
    def __init__(self):
        self.root = TrieNode()  # Empty root represents the empty prefix
    
    def insert(self, word):
        """Insert word into trie - O(m) where m = len(word).
        
        Walkthrough: insert("cat") then insert("car")
          insert("cat"):
            root -> 'c' (create) -> 'a' (create) -> 't' (create, is_end=True)
          insert("car"):
            root -> 'c' (exists) -> 'a' (exists) -> 'r' (create, is_end=True)
          Now 'c' and 'a' nodes are shared between "cat" and "car".
        """
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # Create path if missing
            node = node.children[char]             # Move to child
        node.is_end = True  # Mark the end of a complete word
    
    def search(self, word):
        """Check if exact word exists - O(m).
        
        Critical: search("ca") returns False even though the path exists,
        because node 'a' has is_end=False. Only "cat" and "car" are words.
        """
        node = self._traverse(word)
        return node is not None and node.is_end  # Must be a complete word
    
    def startsWith(self, prefix):
        """Check if any word starts with prefix - O(m).
        
        startsWith("ca") returns True because the path c->a exists,
        even though "ca" itself is not a word.
        """
        return self._traverse(prefix) is not None  # Path existing is enough
    
    def _traverse(self, s):
        """Follow the path for string s. Returns the final node, or None
        if any character along the path does not exist."""
        node = self.root
        for char in s:
            if char not in node.children:
                return None  # Path does not exist
            node = node.children[char]
        return node

class TrieNode:
    __slots__ = ('children', 'is_end')           # cuts memory ~30% in CPython
    def __init__(self):
        self.children = {}                        # char -> TrieNode
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

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

    def search(self, word: str) -> bool:
        node = self._walk(word)
        return node is not None and node.is_end   # complete word, not just a prefix

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None      # path existing is enough

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

def find_words(board, words):
    """Find all words from dictionary in grid.
    
    Strategy: Build trie from word list, then DFS from every cell.
    The trie prunes impossible paths -- if no word starts with the
    current path, we backtrack immediately instead of exploring further.
    """
    # 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)