79. Word Search - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given a 2D grid of characters (board) and a target string (word), determine if the word exists in the grid. The word must be formed by letters of adjacent cells (horizontally or vertically neighboring), and no cell can be used more than once in the word.

Example 1:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
Explanation: The letters A→B→C→C→E→D form the word "ABCCED" along a valid path in the grid.
Example 2:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
Explanation: The letters S→E→E are adjacent in the grid, forming the word "SEE".
Example 3:
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
Explanation: Although the path A→B→C→B seems promising, the letter 'B' at the end would require reusing a cell, which is not allowed.

Constraints:

m == board.length, n == board[i].length
1 ≤ m, n ≤ 6
1 ≤ word.length ≤ 15
The board and word consist of only English letters (uppercase and/or lowercase).

Hints

Scan for the First Letter: Start by scanning the grid for positions that match the first letter of the target word. Each such position is a potential starting point for finding the word.
Depth-First Search (DFS): From a starting cell, try to build the word letter by letter by exploring its neighbors (up, down, left, right). Consider using a recursive DFS that tries all possible directions for the next letter.
Mark Visited Cells: Ensure that you don’t reuse a cell that’s already part of the current word path. Mark a cell as “visited” once you use it, and unmark it (backtrack) if that path doesn’t lead to a solution.
Early Exit on Mismatch: As you build the word, if a letter doesn’t match the current cell or you run out of valid moves, backtrack immediately. This pruning (stopping early) saves time by not exploring impossible paths.
Check Word Completion: If you have matched all characters in the word (reached the word’s length), then you’ve found a valid path — return true. If you exhaust all paths from all starting positions and never match the full word, return false.

Multiple Approaches

1. Brute Force Approach (Exhaustive Search)

A naive brute force solution would involve exploring every possible path in the grid to see if it spells the target word. This means for each cell, trying all sequences of moves (up, down, left, right) of length equal to the word. In the worst case, you’d generate all combinations of moves without any pruning. This approach is conceptually simple but extremely inefficient – most of these paths can be eliminated early because they won’t match the word.

Idea: Pick each cell as a starting point and attempt to build the word by moving in all directions for each subsequent letter. Generate all possible paths of the word’s length.
Why It’s Brute Force: This approach doesn’t use any intelligence about the problem. It blindly tries all sequences of moves, even if the path stops matching the word early on.
Drawbacks: The number of possible paths grows exponentially with the word length. For a word of length k, each step can branch up to 4 ways (up to 4 directions), so there could be up to (4^k) paths from a single start. Most of these are unnecessary to explore once a mismatch is found.

Conclusion: A pure brute force (without early stopping) is impractical. However, we can improve this by integrating checks as we build the path.

2. Optimized Approach (DFS Backtracking with Pruning)

The efficient solution uses backtracking, which is essentially a refined brute force that prunes dead ends early. This approach tries to construct the word letter-by-letter and abandons paths that fail to match.

DFS Backtracking: We perform a Depth-First Search from each cell that matches the first letter of the word. From a cell, we recursively search its neighbors for the next letter, and so on.
Path Construction: We keep an index to track how many letters of the word have been matched so far. At each step, if the current cell’s letter matches word[index], we proceed to explore its neighbors for word[index+1]. If it doesn’t match, we stop exploring that path (prune it).
Marking Visited: To avoid using the same cell twice in one path, we mark the current cell as visited before exploring deeper, and unmark it after exploring (this is the backtracking step where we undo our move). This can be done with a separate visited structure or by temporarily altering the board (e.g., changing the letter to a special character).
Successful Path: If we reach a point where index == len(word), it means we've matched all letters, so we return true to indicate the word is found.
Try Other Paths: If a path does not yield the full word, backtracking will revert the last step and try a different direction. If no direction from a given cell works, the algorithm backtracks to the previous cell, and eventually to trying a new starting cell.
Efficiency Gains: This approach stops exploring a path as soon as a letter doesn’t match, drastically cutting down the search space. It also never revisits a cell in the same path, preventing infinite loops.

Why This is Optimal: In the worst case, we still might explore many paths, but we only explore those that match the word’s prefix so far. There is no known better algorithm for a single word search in an arbitrary grid because in the worst scenario you might have to check all possibilities. Our backtracking ensures we do no more work than necessary.

Code Implementation

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Note: Both implementations use the technique of temporarily marking a cell as visited (by setting it to '#'). This is a common trick to avoid using extra memory for a visited matrix. We ensure to restore the letter after exploring all directions from that cell (backtracking step) so that other paths can use it normally.

Complexity Analysis

Time Complexity: In the worst case, we might explore every possible path in the grid. If (m) is the number of rows, (n) is the number of columns, and (k =) length of the word, the time complexity is about O(m * n * 4^k) in the worst scenario. This comes from the fact that from each cell we can branch into up to 4 directions for each letter of the word. However, because we cannot go back to the immediate previous cell, the branching factor is effectively 3 for subsequent steps (you won’t immediately go back where you came from). A tighter bound is O(m * n * 3^k) , but in big-O terms (3^k) and (4^k) are both exponential. For practical understanding: the algorithm will try at most a constant number of directions (up to 4) for each letter of the word in each cell.
Space Complexity: Aside from the input storage, the main extra space used is the recursion stack and the visited markers. The recursion depth can go up to (k) (the length of the word) in the worst case. We also might use a visited matrix of size m×n or modify the board in place. Thus, the space complexity is O(k) for recursion (and at most O(m*n) if using a separate visited grid). In our implementations, we used in-place marking, so additional space is O(1) beyond the recursion stack. The overall space is therefore O(k) due to recursion depth (which in the worst case could be O(m*n) if the word is as long as all cells).

Step-by-Step Walkthrough with Visuals

Let's walk through an example to see how the backtracking solution finds a word. Consider the board and word from Example 1:

Board:  [ 
  [A, B, C, E],
  [S, F, C, S],
  [A, D, E, E] 
]
Word: "ABCCED"

We need to find "ABCCED" in the board.

Step 1: Find Starting Letter – The first letter is 'A'. We scan the grid for 'A'. The grid has 'A' at positions (0,0) and (2,0). We will try each as a starting point.
- Start at cell (0,0) which contains 'A' – a match for the first letter.
Step 2: Depth-First Search from (0,0) – Now we look for the second letter 'B' in the neighbors of (0,0). The neighbors are (0,1) [right] = 'B', (1,0) [down] = 'S'. Only (0,1) has 'B', which matches. We mark (0,0) as visited and move to (0,1).
Step 3: Continue to Third Letter – From (0,1) ('B'), we look for the third letter 'C'. Neighbors: (0,0) [left] = visited, (0,2) [right] = 'C', (1,1) [down] = 'F'. The valid move is to (0,2) which has 'C'. Mark (0,1) visited, move to (0,2).
Step 4: Fourth Letter – From (0,2) ('C'), look for next letter 'C' (the word has two C's in a row). Neighbors: (0,1) [left] = visited, (0,3) [right] = 'E', (1,2) [down] = 'C', ( - ) [up is out of bounds]. The neighbor (1,2) contains 'C', which matches. Mark (0,2) visited, move to (1,2).
Step 5: Fifth Letter – From (1,2) ('C'), look for 'E'. Neighbors: (1,1) = 'F', (1,3) = 'S', (0,2) = visited, (2,2) = 'E'. The matching neighbor is (2,2) with 'E'. Mark (1,2) visited, go to (2,2).
Step 6: Sixth (Final) Letter – From (2,2) ('E'), look for 'D'. Neighbors: (2,1) = 'D', (2,3) = 'E', (1,2) = visited, (3,2) = out of bounds. We find (2,1) has 'D', a match for the last letter. Mark (2,2) visited, move to (2,1).
Step 7: Word Found – We have now matched all letters "A B C C E D" in sequence. At this point, our index equals the word length, which means the word is found. We return true, and the search terminates successfully.

Throughout this process, if at any step a needed letter wasn’t found among the neighbors, the algorithm would backtrack: unmark the current cell as visited, return to the previous letter’s cell, and try a different direction. If no direction works from a given cell, the algorithm backtracks further to try a new path from an earlier cell, or eventually a new starting cell.

Common Mistakes & Edge Cases

Common Mistakes:

Reusing Cells: A frequent pitfall is forgetting to mark cells as visited (or not marking them properly). This can lead to using the same letter cell multiple times, which violates the rules. Always mark a cell as visited when you go into it, and unmark it when backtracking.
Not Backtracking Properly: If you mark a cell (e.g., change it to '#') and then don’t change it back, it can affect other paths or other starting positions. Ensure that every visit is paired with a corresponding backtrack step to restore state.
Missing Boundary Conditions: It’s easy to write the DFS and forget to check boundary conditions (row/col within valid range) or to check the current letter match before going deeper. This can cause index errors or false matches. Always check boundaries and current cell letter before recursing deeper.
Returning the Result: Another mistake is not returning the result as soon as the word is found. For example, if you find the word in DFS, you should propagate a true result back up and ultimately out of the function. Failing to do so might continue unnecessary searches or even result in the function returning false even though a solution was found. In our code, we handle this by returning true immediately when the last letter is matched.
Global vs Local Visited State: Using a single global visited matrix for all start positions can be tricky. If you don’t reset it between different start attempts, a cell visited in one path might still be marked when exploring a new path from a different start. It’s often easier to manage visited state within the DFS calls (mark and unmark) so that each path exploration is isolated.

Edge Cases to Consider:

Single Cell Board: If the board is 1×1, just check if that single letter matches the word (which would necessarily be of length 1 to return true).
Word Longer than Board Cells: If the word’s length is greater than m*n (total cells in the board), you can return false immediately, because you can’t fit a longer word than the total available letters. For example, a 2x2 board cannot contain a word of length 5.
Multiple Starting Candidates: When the board has repeated letters, the algorithm will try all starting positions. For instance, if the word starts with 'A' and there are many 'A's on the board, each 'A' must be considered. The first successful path (if any) will return true.
No Possible Start: If the first letter of the word isn’t present in the grid at all, the function should quickly return false after scanning the board.
Path That Almost Works: Some paths might share a prefix of the word but then fail near the end. For example, in Example 3 above, "ABCB" shares prefix "ABC" with a path in the board, but fails because the last letter can't be found without reusing a cell. The algorithm correctly backtracks and eventually reports false when no valid path completes the word.
Case Sensitivity: The board can contain uppercase or lowercase, and the word may be given accordingly. Ensure your solution treats them consistently (the given problem treats 'A' vs 'a' as different since it doesn't say case-insensitive).

An illustrative tricky case: consider a board [['a','a']] (two letters in a row) and word = "aaa". A naive search might go a(0,0) -> a(0,1) and then try to go back to a(0,0) for the third 'a'. But that’s not allowed because (0,0) was already used. A correct solution marks visited cells, so it would not count that as a valid path and correctly return false.

Word Search II (LeetCode 212): A harder variation where instead of one word, you have to find all words from a list that appear in the board. This can be solved with backtracking as well, often optimized with a Trie (prefix tree) for pruning multiple word searches simultaneously.
Boggle (Word Game): A classic board game where you find as many words as possible on a letter grid. It’s similar to Word Search II, sometimes allowing diagonal moves. Techniques from Word Search apply here as well.
Number of Islands (LeetCode 200): This problem asks for the number of island regions in a grid of water/land. It uses DFS/BFS on a grid, similar to exploring neighbors in Word Search (though there’s no word matching, just region filling).
Surrounded Regions (LeetCode 130): Another grid DFS/BFS problem where you flip captured regions on a board. It’s not about words, but it reinforces grid traversal techniques.
Backtracking Puzzles: Problems like Sudoku Solver (LeetCode 37) and N-Queens (LeetCode 51) use backtracking in a different context. They are great practice for the kind of systematic search and backtracking used in Word Search. While the board and rules differ, the approach of trying options and backtracking on failure is the same.
Path Finding Problems: If you enjoyed grid path searches, you might also try problems like finding a path in a maze or finding the longest increasing path in a matrix (LeetCode 329). These require exploring grids with certain constraints, akin to how we explore for a word here.