Tries — Master Recap and Interview Cheatsheet

class TrieNode:
    def __init__(self):
        self.children = {}   # char → TrieNode (or [None]*26 for lowercase)
        self.is_end = False  # True when a complete word ends at this node
        # Optional extras:
        # self.count = 0     # words passing through (for prefix count)
        # self.word = ""     # full word (for Word Search II recovery)
 
class Trie:
    def __init__(self):
        self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
 
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end   # must check is_end for exact match
 
    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children:
                return False
            node = node.children[c]
        return True   # no is_end check for prefix

def insert_bit(root, n):
    node = root
    for bit in range(31, -1, -1):
        b = (n >> bit) & 1
        if b not in node.children:
            node.children[b] = {}
        node = node.children[b]
 
def max_xor_query(root, x):
    node = root
    xr = 0
    for bit in range(31, -1, -1):
        b = (x >> bit) & 1
        want = 1 - b   # prefer opposite bit to maximize XOR
        if want in node:
            xr = (xr << 1) | 1
            node = node[want]
        else:
            xr <<= 1
            node = node[b]
    return xr

def findWords(board, words):
    # Build trie with word stored at end nodes
    root = TrieNode()
    for word in words:
        node = root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.word = word   # store word at end for O(1) recovery
 
    result = []
    rows, cols = len(board), len(board[0])
 
    def dfs(r, c, node):
        if not (0 <= r < rows and 0 <= c < cols): return
        ch = board[r][c]
        if ch == '#' or ch not in node.children: return
        next_node = node.children[ch]
        if next_node.word:
            result.append(next_node.word)
            next_node.word = None   # avoid duplicates
        board[r][c] = '#'   # mark visited
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            dfs(r+dr, c+dc, next_node)
        board[r][c] = ch    # restore
 
    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)
    return result