leetcode-212 Word Search II

# Given an m x n board of characters and a list of strings words, return all
# words on the board. Each word must be constructed from letters of sequentially
# adjacent cells, where adjacent cells are horizontally or vertically neighboring.
# The same letter cell may not be used more than once in a word.
#
# Example 1:
# Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],
#        words = ["oath","pea","eat","rain"]
# Output: ["eat","oath"]
#
# Constraints:
# m == board.length
# n == board[i].length
# 1 <= m, n <= 12
# words[i].length <= 10

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None  # Store complete word at end node

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        # Build trie from words
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word  # Mark end and store word

        rows, cols = len(board), len(board[0])
        result = []

        def dfs(r, c, node):
            # Get current character
            char = board[r][c]

            # Check if this path exists in trie
            if char not in node.children:
                return

            # Move to next trie node
            node = node.children[char]

            # Found a complete word
            if node.word:
                result.append(node.word)
                node.word = None  # Avoid duplicates

            # Mark as visited
            board[r][c] = '#'

            # Explore 4 directions
            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)

            # Backtrack: restore character
            board[r][c] = char

            # Optimization: Remove leaf nodes from trie
            if not node.children:
                del node.children[char]

        # Start DFS from each cell
        for r in range(rows):
            for c in range(cols):
                dfs(r, c, root)

        return result

# Time Complexity: O(M * N * 4^L) where M*N is board size, L is max word length
#   (4^L for exploring 4 directions at each step)
# Space Complexity: O(W * L) for trie, where W is number of words
#
# Key Insight: Trie dramatically reduces search space
# Without trie: need to check each word separately
# With trie: prune branches that don't lead to any word
#
# Pattern: Trie + DFS for word search in grid problems