HardBacktracking

Word Search II

Explanation & Solution

Description

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.

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

oath

pea

eat

rain

Output:["eat","oath"]

eat

oath

Explanation: The words "eat" and "oath" can be formed by traversing adjacent cells on the board. "pea" and "rain" cannot be formed.

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⁴
1 <= words[i].length <= 10
words[i] consists of lowercase English letters
All strings in words are unique

Approach

Backtracking pattern

1. Build a Trie from the Word List

Create a trie root node with a children map
For each word in the list, insert it character by character into the trie
Store the complete word at the terminal node (node.word = word) for easy retrieval

2. DFS from Every Cell

Iterate through every cell (r, c) on the board
Start a DFS traversal using the trie root as the starting node
The trie guides the search — only explore paths that match trie branches

3. DFS Traversal Logic

Check bounds and whether the cell has been visited (marked '#')
Check if the current character exists in the trie node's children
If the next trie node has a word property, add it to results and set it to null to avoid duplicates

4. Backtracking

Mark the current cell as visited by replacing its character with '#'
Recursively explore all four directions (up, down, left, right)
Restore the cell's original character after exploring all directions

5. Return Sorted Results

After all DFS traversals complete, sort the result array alphabetically
Return the list of found words

Key Insight

Using a trie to store all target words lets us search for multiple words simultaneously during a single board traversal, avoiding repeated DFS for each word
Setting node.word = null after finding a word prevents duplicate entries without needing a separate set

Time

O(m * n * 4^L) where L is the max word length — but the trie prunes invalid paths early

Space

O(W * L) for the trie, where W is the number of words and L is the average length

Visualization

Input:

DFS Traversal4×4 grid

output—

Press play to start dfs traversal

CurrentQueuedVisitedSource

99 steps

Solution Code

Subsets

Expression Add Operators