Word Search
- mosesg1123
- 4 days ago
- 5 min read
Searching for patterns in a grid under movement constraints shows up in puzzles, pathfinding, and game logic. The “Word Search” problem is a perfect exercise in backtracking over a 2D board with state tracking.
Problem Statement
Given an m × n 2D board of characters and a word, return true if the word exists in the grid. You can construct the word by connecting horizontally or vertically adjacent cells. You may not revisit the same cell within one search.
1. Clarify Requirements Before Jumping Into Code
I want to be sure:
I can start from any cell matching word[0].
Movement is strictly up/down/left/right—no diagonals.
Once I use a cell in the current path, I cannot reuse it.
I return true as soon as one valid path is found; otherwise false.
Grids and word length can be up to a few hundred—exponential paths but pruned quickly.
2. Identify the Category of the Question
This is a grid backtracking problem. Common patterns include:
Depth-first search (DFS) from each candidate starting cell.
Marking cells “visited” during a path and unmarking on backtrack.
Early pruning when characters don’t match or boundaries exceed.
3. Consider a Brute-Force Approach to Understand the Problem
Let's start with a brute-force solution. We'll start with the standard algorithms for searching a grid - Breadth/Depth-First-Search.
If board[i][j] == word[0], start a DFS that tries all four directions.
At each step k in word, scan all four neighbors to match word[k].
Additionally, we'll maintain a "visited" matrix to prevent reuse.
This explores up to 4^L paths per start, where L is word length. This is pretty slow, so let's see if we can do better!
4. Brainstorm More Solutions
Option 1: Optimize on DFS/BFS
There aren't really any algorithms that do better than DFS/BFS when it comes to searching a grid, especially since we aren't talking about a graph with weighted connections between nodes. So the only thing we have left to do is optimize on our brute-force solution. That's what makes this question so interesting in interviews - you get to show off your creativity!
Here are some ideas:
If the board is smaller than the word length, we can immediately return false.
If the letter frequencies on the board don't cover our target words, we can also immediately return false. Of course, that would require us to count all of the characters on the board and store the counts in some kind of data structure, like a hash map or an array.
We can short-circuit out of our DFS algorithm early anytime we encounter a character on the board that does not match the word we are searching for. In other words, if board[i][j] != word[k], prune that branch
To save on space, what if instead of a separate data structure to track 'visited' spaces, we just overwrite the board directly? We can temporarily overwrite board[i][j] with a sentinel (e.g. '#') during the recursive call, then restore. Saves O(m·n) space and simplifies the code.
We could take further advantage of the character frequency check and start our matching from the first or last letter based on which character is rarer. In the worst case though, that doesn't really save any time, and adds to the complexity of the code, so this doesn't feel like a worthwhile optimization.
So to summarize our final solution:
Combine DFS, character frequency checks, early pruning, and in-place marking to track visited spaces
This gives O(m·n·4^L) in the worst case, but with aggressive pruning it runs quickly for typical constraints.
Option 2: Tries
We know Tries are an excellent choice when we encounter questions that require flexible string comparisons. So, can we take advantage of a trie in this question?
What if we populate our trie with every possible "word" in the word search? We would iterate over every character in the grid, then using DFS or BFS, traverse the grid and fill out our trie with every possible branch. That would take O(∑L) (i.e. the sum of all possible words). Then, searching for your target word only takes O(L) time!
Now, the obvious next question here is, does that actually save time? Then answer is: it depends!
You'll need to consider the constraints of your problem statement when considering whether to choose a trie vs. straight-DFS.
For example, do we have a very large grid with many possible words? Then building a Trie might be too expensive.
On the other hand, if we knew we only have a single grid that we are going to search many times with many possible target words, then in the long run, we might actually save time by pre-processing the grid in order to optimize the runtime of our search API.
Given the exact wording of this exact problem, Option 1 is preferable, since we should expect to have many different grids of indeterminate size.
5. Discuss Trade-Offs Between Your Solutions
Approach | Time Complexity | Space Complexity | Pros | Cons |
Brute-force DFS | O(m·n·4^L) | O(m·n + L) | Conceptually simple | Explodes on large L |
DFS + in-place marking | O(m·n·4^L) (pruned heavily) | O(L) | No extra board memory, good pruning | Still exponential worst case |
DFS + heuristic reverse comparison | O(m·n·4^L) (more pruned) | O(L) | Reduces branching when one end is rarer | Added complexity to decide search direction |
Trie of words + single pass | O(∑L) | O(total letters) | Useful when searching many words at once | Overkill for single-word search |
6. Write Pseudocode to Structure Your Thoughts
function exist(board, word):
if total cells < word.length: return false
if letter frequencies insufficient: return false
for each cell (i,j):
if board[i][j] == word[0]:
if dfs(i, j, 0): return true
return false
function dfs(i, j, k):
if k == word.length: return true
if out of bounds or board[i][j] != word[k]: return false
temp = board[i][j]
board[i][j] = '#' // mark visited
for each (di,dj) in [(1,0),(-1,0),(0,1),(0,-1)]:
if dfs(i+di, j+dj, k+1):
board[i][j] = temp
return true
board[i][j] = temp // restore
return false
7. Consider Edge Cases
Empty word "" → return true by definition.
Word length 1 → any matching cell suffices.
Board with all identical letters and repeated word letters → heavy pruning needed.
Word longer than number of cells → return false immediately.
8. Write Full Code Syntax
public class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
if (word.length() > m * n) return false;
// Optional frequency check
int[] freq = new int[26];
for (char[] row : board)
for (char c : row) freq[c - 'A']++;
for (char c : word)
if (--freq[c - 'A'] < 0) return false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == word.charAt(0) && dfs(board, i, j, 0, word))
return true;
}
}
return false;
}
private boolean dfs(char[][] board, int i, int j, int k, String word) {
if (k == word.length()) return true;
int m = board.length, n = board[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != word.charAt(k))
return false;
char saved = board[i][j];
board[i][j] = '#';
boolean found = dfs(board, i+1, j, k+1, word)
|| dfs(board, i-1, j, k+1, word)
|| dfs(board, i, j+1, k+1, word)
|| dfs(board, i, j-1, k+1, word);
board[i][j] = saved;
return found;
}
}
9. Test Your Code
public static void main(String[] args) {
Solution sol = new Solution();
char[][] b = {
{'A','B','C','E'},
{'S','F','C','S'},
{'A','D','E','E'}
};
System.out.println(sol.exist(b, "ABCCED")); // true
System.out.println(sol.exist(b, "SEE")); // true
System.out.println(sol.exist(b, "ABCB")); // false
System.out.println(sol.exist(b, "")); // true
System.out.println(sol.exist(new char[][]{{'A'}}, "A")); // true
System.out.println(sol.exist(new char[][]{{'A'}}, "B")); // false
}
10. Key Lessons to Remember for Future Questions
Backtracking with in-place marking is memory-efficient.
Early pruning by letter-frequency check can save huge search.
Always restore state on backtrack to allow other paths.
Testing empty and singleton cases validates boundary logic.
This pattern extends to many maze and grid-search problems.
Good Luck and Happy Coding!
留言