Word Search II

Problem

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"]

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 10^4
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

Solution

Approach: Trie + DFS Backtracking

The key insight is to build a trie from all words, then DFS from each cell while traversing the trie. This allows us to search for all words simultaneously.

Implementation

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
        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

        m, n = len(board), len(board[0])
        result = []
        visited = set()

        def dfs(r, c, node):
            # Bounds check and visited check
            if (r < 0 or r >= m or c < 0 or c >= n or
                (r, c) in visited or board[r][c] not in node.children):
                return

            visited.add((r, c))
            node = node.children[board[r][c]]

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

            # Explore all 4 directions
            dfs(r + 1, c, node)
            dfs(r - 1, c, node)
            dfs(r, c + 1, node)
            dfs(r, c - 1, node)

            visited.remove((r, c))

        # Start DFS from each cell
        for i in range(m):
            for j in range(n):
                dfs(i, j, root)

        return result

Optimized Version (With Pruning):

class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        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

        m, n = len(board), len(board[0])
        result = []

        def dfs(r, c, node):
            if r < 0 or r >= m or c < 0 or c >= n:
                return

            char = board[r][c]
            if char not in node.children:
                return

            node = node.children[char]

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

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

            # Explore 4 directions
            dfs(r + 1, c, node)
            dfs(r - 1, c, node)
            dfs(r, c + 1, node)
            dfs(r, c - 1, node)

            # Restore
            board[r][c] = char

            # Prune: remove leaf nodes
            if not node.children:
                del node.children[char]

        for i in range(m):
            for j in range(n):
                dfs(i, j, root)

        return result

Complexity Analysis

Time Complexity: O(m * n * 4^L), where m*n is board size and L is the max word length. We explore 4 directions up to L depth from each cell.
Space Complexity: O(w * L), where w is the number of words and L is the average word length (for the trie).

Key Insights

Trie for Multiple Words: Building a trie allows us to search for all words simultaneously in a single DFS pass, much more efficient than searching for each word individually.
DFS from Every Cell: We start DFS from each cell because a word can start anywhere on the board.
Backtracking Pattern: We mark cells as visited during DFS and unmark when backtracking to allow other paths to use them.
Word Storage in Trie: Storing the complete word at the end node makes it easy to add to results without reconstructing.
Pruning Optimization: Removing found words from the trie and pruning empty branches reduces unnecessary exploration.
Avoiding Duplicates: Setting node.word = None after finding a word prevents adding the same word multiple times if it appears on different paths.