Word Search
Medium Grid DFS backtracking
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Decide whether a word can be traced in a letter grid by moving up, down, left or right, without reusing a cell.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: can you trace the word through neighbouring cells without reusing a cell?
Why this works: DFS from each matching start cell; mark cells on the current path and unmark them when you go back.
Example: word "SEE" on [[A,B,C,E],[S,F,C,S],[A,D,E,E]]
start S at (1,3) → E at (2,3) → E at (2,2) ✓✦Hints open one at a time
↗Approach
dfs(r, c, i): fail if out of bounds or the letter doesn't match word[i]. If i is the last index, succeed. Temporarily replace the cell with '#', try four neighbours, then restore.
</>Solution (Java)
class Solution {
public boolean exist(char[][] board, String word) {
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
if (dfs(board, word, r, c, 0)) return true;
return false;
}
private boolean dfs(char[][] b, String w, int r, int c, int i) {
if (r < 0 || c < 0 || r >= b.length || c >= b[0].length || b[r][c] != w.charAt(i)) return false;
if (i == w.length() - 1) return true;
char saved = b[r][c];
b[r][c] = '#'; // mark visited
boolean found = dfs(b, w, r + 1, c, i + 1) || dfs(b, w, r - 1, c, i + 1)
|| dfs(b, w, r, c + 1, i + 1) || dfs(b, w, r, c - 1, i + 1);
b[r][c] = saved; // restore
return found;
}
}!Common mistake
Forgetting to restore the cell, which blocks other paths that need it.
- Time: O(m · n · 3^L), L = word length.
- Space: O(L) recursion.