Problem Statement

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.

Additional information

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

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: []

Explanation: You cannot reuse the "b" cell or the "c" cell to spell "abcb".

Trie (Prefix Tree) + Backtracking DFS - Optimal

Intuition

A naive approach would be to run a standard Word Search (DFS) for every single word in the words list. If the board is large and the list of words is huge, this results in massive duplicate work (e.g., searching for "app", "apple", and "apply" would restart the search three times).

To optimize this, we can build a Trie (Prefix Tree) out of the words list.
By doing this, we can run a single Depth-First Search (DFS) from each cell on the board. As we traverse the grid, we simultaneously walk down the Trie. If the current sequence of letters on the board forms a valid prefix in our Trie, we keep going. If it hits a dead end in the Trie, we immediately stop searching that path.

Algorithm

1. Build the Trie:

   • Create a TrieNode class (which holds a dictionary of children and a boolean is_word).
   • Insert every word from words into the Trie.

2. DFS Setup:

   • Initialize a res set to hold the found words (to avoid duplicates).
   • Store the ROWS and COLS of the board.

3. DFS Function (dfs(r, c, node, word)):

   • Base Cases / Pruning: If the row r or column c is out of bounds, or the current character is not a child of the current Trie node, or the cell has been visited (e.g., marked as "#"), return immediately.
   • Process Node:
     • Get the character from board[r][c].
     • Move to the next Trie node: next_node = node.children[char].
     • Append the character to our current word string.
   • Found a Word: If next_node.is_word is True, add word to res. (Optimization: Set next_node.is_word = False so we don't add it again and can potentially prune the tree).
   • Backtrack:
     • Mark the current cell as visited: board[r][c] = "#".
     • Recursively call dfs on the 4 neighboring cells (up, down, left, right).
     • Unmark the cell: board[r][c] = char.
   • Pruning Optimization: If next_node has no more children, we can delete it from node.children to speed up future DFS paths.

4. Execute: Loop through every row and column, calling dfs starting at the Trie's root.

5. Return list(res).

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

def find_words(board: list[list[str]], words: list[str]) -> list[str]:
    # 1. Build the 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.is_word = True
        
    res = set()
    ROWS, COLS = len(board), len(board[0])
    
    # 2. Backtracking DFS
    def dfs(r, c, node, word):
        if (r < 0 or r == ROWS or c < 0 or c == COLS or 
            board[r][c] not in node.children):
            return
            
        char = board[r][c]
        next_node = node.children[char]
        word += char
        
        # Word found
        if next_node.is_word:
            res.add(word)
            next_node.is_word = False # Prevent duplicates
            
        # Mark as visited
        board[r][c] = "#"
        
        # Explore neighbors
        dfs(r + 1, c, next_node, word)
        dfs(r - 1, c, next_node, word)
        dfs(r, c + 1, next_node, word)
        dfs(r, c - 1, next_node, word)
        
        # Unmark (Backtrack)
        board[r][c] = char
        
        # Optimization: prune empty branches from the Trie
        if not next_node.children:
            del node.children[char]
            
    # 3. Search from every cell
    for r in range(ROWS):
        for c in range(COLS):
            dfs(r, c, root, "")
            
    return list(res)

Time & Space Complexity

• Time complexity: O(M * N * 4^L)

  • Reason: M * N is the size of the board. From each cell, we can theoretically branch out in 4 directions up to a length of L (the maximum length of a word). However, the Trie heavily prunes invalid paths, so the average runtime is significantly faster than the upper bound. Building the Trie takes O(W * L) where W is the number of words.

• Space complexity: O(W * L)

  • Reason: Building the Trie consumes O(W * L) space to store all the characters. The recursion stack for the DFS uses up to O(L) space.