Word Search II

PracticeNeetCode ↗LeetCode ↗

Given an m × n grid of characters board and a list of strings words, return every word from the list that can be traced through a path of adjacent cells (up, down, left, right), using each cell at most once per word.

Example

Key Pointers

• Running a fresh DFS from every cell for every word separately wastes work when many words share prefixes — build one trie from all of words so shared prefixes are only explored once.
• Store the actual word (not just a flag) at the trie node where it ends, so a match hands you the answer directly.
• Clear a word from its trie node once it's found, so it can't be added to the result twice via a different path.
• Mark cells visited during the DFS and unmark on backtrack — same discipline as single-word Word Search.

Step-by-Step Analysis

1. Insert every word into a trie, storing the word itself at its terminal node.
2. For each cell in the board whose character is a child of the trie root, start a DFS from that cell with the matching trie node.
3. In the DFS: move to the trie child matching the current cell's character; if that node stores a word, append it to the result and clear it.
4. Recurse into the four neighboring cells that are in bounds, unvisited, and whose character exists as a child of the current trie node.
5. Unmark the current cell (backtrack) before returning from each call.

Complexity

Time: O(m · n · 4^L) worst case, where L is the longest word's length — Space: O(N · L) for the trie, O(L) recursion depth

Code

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.word: str | None = None


def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    root = TrieNode()
    for w in words:
        node = root
        for ch in w:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.word = w

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

    def dfs(r: int, c: int, node: TrieNode) -> None:
        if (
            r < 0 or c < 0 or r >= rows or c >= cols
            or (r, c) in visited
            or board[r][c] not in node.children
        ):
            return

        ch = board[r][c]
        nxt = node.children[ch]
        if nxt.word is not None:
            result.append(nxt.word)
            nxt.word = None

        visited.add((r, c))
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            dfs(r + dr, c + dc, nxt)
        visited.remove((r, c))

    for r in range(rows):
        for c in range(cols):
            dfs(r, c, root)

    return result

Code Explanation

How the solution above works, piece by piece.

1. Build one trie from all the words; the node at the end of each word stores the word itself.
2. dfs(r, c, node) tries to extend the current trie path with the letter at (r, c). It stops if the cell is off the board, already on the path, or the letter isn't a child of node.
3. If the new node holds a word, record it and set word = None so it isn't reported twice.
4. Mark the cell visited, explore the 4 neighbours, then unmark it (backtracking) so other paths may use it.
5. Start a DFS from every cell. The trie shares prefixes between words and cuts off dead paths early, far better than searching each word separately.

Visual Walkthrough

Running it on the example board and words:

Video Explanation

NeetCode — Backtracking Trie, LeetCode 212