HardTrieBacktrackingDepth-First SearchMatrix

Word Search II

1 approach, code in every language

You are given an m x n grid of lowercase letters and a list of target words. A word is present in the grid if its letters can be spelled out by moving through a sequence of adjacent cells, where adjacent means horizontally or vertically neighboring. The same cell cannot be reused within a single word.

Return every word from the list that can be formed this way. The order of the returned words does not matter, and each found word should appear only once.

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: ['oath','eat']

'oath' traces through connected cells starting at the top-left, and 'eat' can be spelled out; 'pea' and 'rain' have no valid connected path.

Example 2

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

Output: []

Forming 'abcb' would require revisiting the cell holding 'b', which is not allowed, so no word is returned.

Constraints

m == board.length and n == board[i].length
1 ≤ m, n ≤ 12
1 ≤ words.length ≤ 3 * 10^4
1 ≤ words[i].length ≤ 10

Trie + Backtracking DFS

Insert all target words into a trie, then run a DFS from every cell that only continues along paths matching a trie branch, collecting words as their end markers are reached.

Loading animation…

Intuition

Searching for each word independently repeats a lot of work when words share prefixes. A trie collapses those shared prefixes into a single structure, so one grid traversal can pursue many candidate words at once. As the DFS walks the board, it moves in lockstep with the trie: if the current letter is not a child of the current trie node, that path cannot spell any target and is abandoned immediately. When we land on a trie node that marks the end of a word, we record it. Marking cells as visited during recursion prevents reusing a cell, and clearing an end marker after collecting its word avoids duplicate results.

Algorithm walkthrough

1Build a trie from all target words, storing the full word at the node that ends it.
2Start a DFS from each grid cell, guided by the trie root.
3At each step, check that the current letter matches a child of the current trie node; if not, prune this branch.
4When a node's stored word is non-empty, add it to the results and clear the marker to prevent duplicates.
5Temporarily mark the cell as visited, recurse into the four neighbors, then restore the cell so other paths can use it.

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:
                node = node.children.setdefault(ch, TrieNode())
            node.word = word

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

        def dfs(r: int, c: int, node: TrieNode) -> None:
            ch = board[r][c]
            nxt = node.children.get(ch)
            if nxt is None:
                return
            if nxt.word is not None:
                result.append(nxt.word)
                nxt.word = None
            board[r][c] = '#'
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != '#':
                    dfs(nr, nc, nxt)
            board[r][c] = ch

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

Time

O(m * n * 4 * 3^(L-1)) where L is the longest word length

Space

O(total characters across all words) for the trie plus O(L) recursion depth

The trie prunes impossible branches early, so real-world runs explore far fewer paths than the worst-case bound.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Letter Plate Catalogue is our own problem on the technique behind Word Search II: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free