LeetCode 212: Word Search II

Problem Restatement

We are given:

board
words

board is an m x n grid of characters.

words is a list of strings.

We need to return all words from words that can be formed on the board.

A word can be formed by moving from one cell to another adjacent cell.

Allowed moves:

up
down
left
right

Diagonal moves are not allowed.

The same board cell cannot be used more than once in the same word.

The official statement says: given an m x n board of characters and a list of strings words, return all words on the board. Each word must be built from sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring, and the same cell cannot be used more than once in one word.

Input and Output

Example function shape:

def findWords(board: list[list[str]], words: list[str]) -> list[str]:
    ...

Examples

Example 1:

board = [
    ["o","a","a","n"],
    ["e","t","a","e"],
    ["i","h","k","r"],
    ["i","f","l","v"],
]
words = ["oath", "pea", "eat", "rain"]

Output:

["oath", "eat"]

"oath" can be formed by adjacent cells.

"eat" can also be formed.

"pea" and "rain" cannot be formed by a valid path.

Example 2:

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

Output:

[]

The letters exist, but forming "abcb" would require reusing the b cell.

Cell reuse is not allowed.

First Thought: Search Each Word Separately

A direct approach is:

1. For each word in words.
2. Run DFS from every board cell.
3. Check whether that word exists.

This is similar to LeetCode 79: Word Search.

Pseudo-code:

for word in words:
    search word on board using DFS

This works, but it repeats many searches.

For example, if many words share prefixes:

["app", "apple", "apply"]

searching each word independently repeats the same prefix path:

a -> p -> p

many times.

Problem With Brute Force

Let:

R = number of rows
C = number of columns
W = number of words
L = average word length

Searching each word separately can be expensive.

For each word, DFS may branch in up to four directions.

A rough upper bound is:

O(W * R * C * 4^L)

That is too slow when there are many words.

We need to search all words together.

Key Insight: Trie Plus Board DFS

A Trie stores all words by prefix.

When we explore paths on the board, we also walk through the Trie.

This gives two major benefits:

Example words:

["oath", "pea", "eat", "rain"]

The Trie stores these words as paths.

During DFS, if the current board path is:

oa

and no word starts with "oa", we stop exploring that path.

If a path reaches a Trie node that marks the end of a word, we found a word.

Trie Node Design

Each node needs:

We store the full word at the terminal node.

That makes adding to the answer simple.

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

If node.word is not None, then the current path forms a complete word.

Algorithm

1. Build a Trie from all words.
2. Start DFS from every board cell.
3. During DFS:
   • Check whether the current character exists in the current Trie node.
   • If not, stop.
   • Move into the child Trie node.
   • If the child node contains a word, add it to the result.
   • Mark the board cell as visited.
   • Explore four neighbors.
   • Restore the board cell.
4. Return the result list.

Walkthrough

Use:

board = [
    ["o","a","a","n"],
    ["e","t","a","e"],
    ["i","h","k","r"],
    ["i","f","l","v"],
]
words = ["oath", "pea", "eat", "rain"]

Build a Trie.

Important paths:

o -> a -> t -> h  word = "oath"
e -> a -> t       word = "eat"
p -> e -> a       word = "pea"
r -> a -> i -> n  word = "rain"

Start DFS from cell (0, 0):

board[0][0] = "o"

"o" exists in the Trie, so continue.

Move right to (0, 1):

path = "oa"

"oa" exists in the Trie.

Move down to (1, 1):

path = "oat"

"oat" exists.

Move down to (2, 1):

path = "oath"

This Trie node has:

word = "oath"

So we add "oath" to the answer.

The DFS continues, but any path that stops matching a Trie prefix is pruned.

Avoiding Duplicate Results

The same word might be reachable through multiple paths, or a word might appear more than once in the board.

After finding a word, we can set:

node.word = None

This prevents adding the same word twice.

This does not break Trie traversal, because the node and its children remain in place.

Correctness

The Trie contains every word from words, represented by one path per word.

The DFS explores all valid board paths. A valid path moves only up, down, left, or right, and the algorithm marks cells as visited so the same cell cannot be reused in the same path.

At each step, the DFS also follows the corresponding Trie path. If the board path is not a prefix of any word, the DFS stops. This only removes paths that cannot possibly form a word.

Whenever the DFS reaches a Trie node whose word field is set, the current board path spells a full word from the input list, so adding it is correct.

Conversely, suppose a word from words can be formed on the board. Its board path will be explored by DFS from its first cell. Since the word was inserted into the Trie, every prefix of that word exists in the Trie, so the DFS will not prune the path before reaching the final character. At the final Trie node, the word will be found.

Therefore the algorithm returns exactly the words from words that can be formed on the board.

Complexity

Let:

R = number of rows
C = number of columns
S = total number of characters across all words
L = maximum word length

The worst-case DFS bound is loose. In practice, the Trie prunes many paths early.

Also, after the first DFS step, there are at most three useful directions because we cannot immediately go back to the previous cell.

Implementation

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 ch in word:
                if ch not in node.children:
                    node.children[ch] = TrieNode()

                node = node.children[ch]

            node.word = word

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

        def dfs(r: int, c: int, node: TrieNode) -> None:
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return

            ch = board[r][c]

            if ch == "#":
                return

            if ch not in node.children:
                return

            next_node = node.children[ch]

            if next_node.word is not None:
                result.append(next_node.word)
                next_node.word = None

            board[r][c] = "#"

            dfs(r + 1, c, next_node)
            dfs(r - 1, c, next_node)
            dfs(r, c + 1, next_node)
            dfs(r, c - 1, next_node)

            board[r][c] = ch

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

        return result

Code Explanation

Create the Trie root:

root = TrieNode()

Insert each word:

for word in words:
    node = root

    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()

        node = node.children[ch]

    node.word = word

The line:

node.word = word

marks the final node of a word.

The DFS first checks boundaries:

if r < 0 or r >= rows or c < 0 or c >= cols:
    return

Then it checks whether the cell is already visited:

if ch == "#":
    return

Then it checks whether the current character can continue any Trie prefix:

if ch not in node.children:
    return

Move to the matching Trie child:

next_node = node.children[ch]

If the node stores a word, we found one:

if next_node.word is not None:
    result.append(next_node.word)
    next_node.word = None

Mark the board cell as visited:

board[r][c] = "#"

Explore all four directions:

dfs(r + 1, c, next_node)
dfs(r - 1, c, next_node)
dfs(r, c + 1, next_node)
dfs(r, c - 1, next_node)

Restore the original character:

board[r][c] = ch

Finally, start DFS from every cell:

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

Optional Pruning

We can remove leaf nodes from the Trie after exploring them.

This reduces future work.

if not next_node.children and next_node.word is None:
    del node.children[ch]

Place this after restoring the board cell.

Full modified ending:

board[r][c] = ch

if not next_node.children and next_node.word is None:
    del node.children[ch]

This is safe because the child node no longer leads to any unfound word.

Testing

def run_tests():
    s = Solution()

    board = [
        ["o","a","a","n"],
        ["e","t","a","e"],
        ["i","h","k","r"],
        ["i","f","l","v"],
    ]
    words = ["oath", "pea", "eat", "rain"]
    assert sorted(s.findWords(board, words)) == ["eat", "oath"]

    board = [["a","b"],["c","d"]]
    words = ["abcb"]
    assert s.findWords(board, words) == []

    board = [["a"]]
    words = ["a", "b"]
    assert s.findWords(board, words) == ["a"]

    board = [["a","a"]]
    words = ["a", "aa", "aaa"]
    assert sorted(s.findWords(board, words)) == ["a", "aa"]

    print("all tests passed")

run_tests()