Word Search
Understanding the Problem
We are given a 2D grid of characters and a target word. We need to determine if we can trace out the word by moving through adjacent cells (up, down, left, right), using each cell at most once per path.
This is a path-finding problem on a grid. We are looking for a specific sequence of characters, and at each step we can only move to a neighboring cell. The no-reuse constraint means we have to track which cells are currently part of the path, since the same cell could be a valid neighbor on a different path but not twice on the same one.
That structure points to backtracking. We build the word one character at a time, exploring the four directions from the current cell. When a branch hits a dead end (no neighbor matches the next character), we undo the last step and try a different direction. The small grid (at most 6x6) keeps the exponential search tractable, so backtracking is the practical choice here.
Key Constraints:
1 <= m, n <= 6→ The grid has at most 36 cells. An exponential backtracking search is affordable at this size, which rules out the need for a more elaborate algorithm.1 <= word.length <= 15→ Since each cell is used at most once per path, any matching path has length at most 36, so a 15-character word is always within reach if the characters line up.boardandwordconsist of only lowercase and uppercase English letters → The matching is case-sensitive, so'a'and'A'are different characters.
Approach 1: Brute Force (Generate All Paths)
Intuition
Generate every possible path whose length equals the word's length, starting from every cell, and check whether any of those paths spells out the target word. At each cell we branch into all four directions, appending characters to a running string. When the string reaches the word's length, we compare it against the word.
This is DFS without early termination. We never check whether the current partial path is still a valid prefix of the word, so we build out full paths and only compare at the end. It produces the correct answer but explores many paths that diverged from the word at the very first character.
Algorithm
- For each cell (i, j) in the grid, start a DFS.
- In the DFS, maintain a visited set and a current path string.
- At each step, move to all four unvisited neighbors, appending their character to the path.
- When the path length equals the word length, check if the path matches the word.
- If any path matches, return true. Otherwise, backtrack (remove the cell from visited and the character from the path) and try the next direction.
- If no starting cell produces a matching path, return false.
Example Walkthrough
Code
- Time Complexity: O(m n 4^L). We try each of the m*n cells as a starting point. From each cell, we explore up to 4 directions at each step, and the path can be up to L characters long. Since we do not prune based on character matching, we explore many dead-end paths.
- Space Complexity: O(m n + L). The visited matrix takes O(m n) space. The recursion stack can go up to L levels deep, and string concatenation adds O(L) per call.
The next approach prunes the search by checking each character as it goes, abandoning a branch the moment a cell fails to match the expected character.
Approach 2: Backtracking with Character-by-Character Matching (Optimal)
Intuition
Instead of building a full path and comparing at the end, check character by character as the DFS descends. At each step, verify that the current cell holds the expected character of the word at the current position. If it does not match, return false and stop exploring that branch.
That single check prunes the search tree. When board[i][j] does not equal word[index], none of the four directions from this cell can lead to a match, so they are never explored. The search now only follows paths that are valid prefixes of the word, which is far fewer than the blind enumeration of Approach 1.
For visited tracking, instead of a separate boolean matrix, we modify the board in place. When we enter a cell, we save its character and overwrite it with a sentinel marker ('#'). The recursive calls treat that marked cell as a non-match (it equals no letter of the word), so the path cannot revisit it. When the call returns, we restore the original character.
The in-place marking is safe because the board contains only English letters, so the sentinel '#' never equals a real word character. A marked cell therefore fails the board[i][j] != word[index] check on any recursive call, which is what prevents a path from reusing it. Restoring the character after the recursive calls return means the board is unchanged once exist finishes, so a starting cell that failed does not corrupt the board for the next starting cell.
The || chain short-circuits: the first direction that returns true stops the remaining directions from running, so a found word returns up the stack immediately.
Algorithm
- For each cell (i, j) in the grid, check if
board[i][j]matchesword[0]. If so, start a DFS from that cell. - In the DFS, accept the current position (i, j) and the current index into the word.
- If the index equals the word length, we have matched all characters. Return true.
- If (i, j) is out of bounds, or the cell is already visited, or
board[i][j]does not matchword[index], return false. - Mark the cell as visited by saving its character and replacing it with
'#'. - Recursively explore all four directions with
index + 1. - If any direction returns true, return true.
- Otherwise, restore the cell's original character (backtrack) and return false.
Example Walkthrough
Code
- Time Complexity: O(m n 3^L). We try each of the m*n cells as a starting point. From the first cell, we can go in 4 directions, but from every subsequent cell, we can only go in 3 directions (we cannot go back to where we came from, since that cell is marked as visited). The total work per starting cell is O(3^L). In practice, character mismatches prune most branches.
- Space Complexity: O(L). The recursion stack can go up to L levels deep, where L is the length of the word. We modify the board in-place for visited tracking, so no additional data structure is needed.
This is the standard optimal solution. The next approach keeps the same backtracking core but adds cheap preprocessing that rejects impossible inputs up front and reduces the number of cells the DFS starts from.
Approach 3: Backtracking with Pruning Optimizations
Intuition
The backtracking from Approach 2 already has the best worst-case complexity available for this problem. The improvements here do not change that bound, but they cut the average-case work with two pieces of preprocessing.
The first is a frequency check. Count how many times each character appears in the board, then walk the word and tally its characters. If the word needs more of any character than the board contains (it needs five 'A's but the board has three), no path can spell it, so we return false before running any DFS.
The second concerns which end of the word to search from. A path that spells word forwards from a starting cell also spells the reversed word backwards from the same path's end. So searching for the reversed word gives the same answer, but the DFS now starts only from cells matching the word's last character. If the last character is rarer in the board than the first, reversing reduces the number of starting cells, and fewer starting cells means fewer top-level DFS calls.
Adjacency in the grid is symmetric: if cell A is a neighbor of cell B, then B is a neighbor of A. So a sequence of cells that spells word reading forward spells reverse(word) reading backward, over the exact same cells. The set of valid paths is identical; only the direction we walk them changes. Reversing the word therefore cannot change the true/false answer.
What it changes is the starting set. The DFS launches from every cell matching the search word's first character. Consider a board that is mostly 'A' with a word that starts with 'A' and ends with 'Z'. Searching forward starts the DFS from nearly every cell; searching the reversed word starts only from the few 'Z' cells. The worst-case bound is unchanged, but fewer top-level calls means less work on inputs like this.
Algorithm
- Count the frequency of each character in the board.
- For each character in the word, check if the board has enough of that character. If not, return false immediately.
- Count how many cells match
word[0]versusword[word.length - 1]. If the first character has more matches, reverse the word to start the search from the rarer end. - Run the same backtracking DFS as Approach 2.
Example Walkthrough
Code
- Time Complexity: O(m n 3^L). The preprocessing (frequency counting and reversal) takes O(m * n + L), which is negligible compared to the DFS. The DFS itself has the same worst-case complexity as Approach 2. However, the pruning makes the average case dramatically faster.
- Space Complexity: O(L). Same as Approach 2. The frequency arrays use O(1) extra space (fixed size 128), and we modify the board in-place. The recursion stack is O(L).