Word Search
The Prompt
Given an `m x n` grid of characters `board` and a string `word`, return `true` if `word` exists in the grid. The word can 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.
Understanding the Problem
You are looking for a path in the grid that spells the word, moving only up/down/left/right and never standing on the same cell twice. Any cell matching the first letter could be the start, and each subsequent letter narrows the walk — a textbook depth-first search where the state is (row, col, index-into-word).
The "no reuse" rule is what makes it backtracking rather than plain DFS: before exploring a cell’s neighbors, mark the cell visited (overwrite it with "#"), and after all four directions return, restore the original letter. That way the cell is blocked for the current path but free for every other path.
The Interview Flow
Interviewer
Given a 2D board of characters and a word, how do you check if the word can be formed by adjacent letters?
Candidate
I need to search for a path in the grid that spells out the word. This is a classic backtracking problem that can be solved with Depth-First Search (DFS).
Interviewer
How would you structure the search?
Candidate
I would iterate through every cell on the board. If a cell contains the first letter of the word, I would start a DFS from that cell to see if I can find the rest of the word.
Interviewer
Describe the DFS function. What state does it need, and what are its base cases?
Candidate
The DFS function would need the current row, column, and the index of the character in the word I'm currently looking for. The base cases are: 1) If the index reaches the end of the word, I've successfully found it, so return true. 2) If the current cell is out of bounds or its character doesn't match the character I'm looking for, this path is invalid, so return false.
Interviewer
The problem says you can't use the same letter cell more than once. How do you handle that?
Candidate
To prevent reusing a cell in the current path, I need to mark it as visited before I explore its neighbors. A simple way is to temporarily modify the character on the board to a special character, like "#". After the recursive calls for its neighbors return, I must "backtrack" by restoring the original character, so that it can be used in other potential paths.
Interviewer
That's a complete plan. It correctly uses backtracking to explore paths and handle the visited state. Please proceed.
Why is marking and restoring cells both necessary and sufficient?
The invariant during DFS: the cells currently overwritten with "#" are exactly the cells on the current partial path, and they spell word[0..index-1]. Marking prevents the path from crossing itself; restoring on the way out guarantees a failed exploration leaves the board exactly as it found it, so other starting points and directions see a clean grid. Miss the restore and you silently forbid valid answers.
The cost: from each of the m·n starting cells, the DFS branches up to 3 ways per letter (you never go back the way you came), giving O(m·n·3^L) time for a word of length L — exponential in L but with L ≤ 15-ish in practice. Space is just the O(L) recursion stack, since visited-marking lives in the board itself.
Recursive Backtracking (DFS)
- Iterate through each cell `(r, c)` of the `board`.
- If `board[r][c]` matches the first character of the `word`, start a DFS search from this cell.
- If the DFS search returns `true`, it means the word was found, so return `true` immediately.
- If the loops finish without the DFS ever returning `true`, the word is not in the board, so return `false`.
- **DFS Helper `dfs(r, c, index)`:**
- Base Case 1 (Success): If `index` equals the length of `word`, we have found the entire word. Return `true`.
- Base Case 2 (Failure): Check if `(r, c)` is out of bounds or if `board[r][c]` does not match `word[index]`. If so, return `false`.
- Mark the current cell as visited: `char temp = board[r][c]; board[r][c] = '#';`
- Explore neighbors recursively: Call `dfs` for `(r+1, c)`, `(r-1, c)`, `(r, c+1)`, `(r, c-1)`, each with `index + 1`. If any of these calls return `true`, store the result in a boolean variable.
- Backtrack: Restore the original character: `board[r][c] = temp;`
- Return the result from the exploration step.
Try it yourself
Write your solution and run it against 3 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
function dfs(r, c, i) {
if (i === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) {
return false;
}
const temp = board[r][c];
board[r][c] = '#'; // Mark as visited
const found = dfs(r + 1, c, i + 1) ||
dfs(r - 1, c, i + 1) ||
dfs(r, c + 1, i + 1) ||
dfs(r, c - 1, i + 1);
board[r][c] = temp; // Backtrack
return found;
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (board[r][c] === word[0] && dfs(r, c, 0)) {
return true;
}
}
}
return false;
}Explanation
Search for "ABCCED" in the grid [[A,B,C,E],[S,F,C,S],[A,D,E,E]] — the cells below show how much of the word the DFS has matched.
1Scan the grid for the first letter. Cell (0,0) holds "A" — match word[0], mark (0,0) as "#", and recurse on its neighbors.
2Move right: (0,1) = "B" matches word[1], then (0,2) = "C" matches word[2]. Three cells are now marked; the path so far is A → B → C along the top row.
3From (0,2), right gives "E" ≠ "C" — dead end, backtrack. Down to (1,2) = "C" matches word[3], then down again to (2,2) = "E" matches word[4].
4Left to (2,1) = "D" matches word[5], the final letter — index reaches the word length, so return true and unwind, restoring every "#" on the way out.
Complexity Analysis
TIME
O(m*n*4^l)
SPACE
O(l)
Finished working through this one?
Mark it complete to track it on your Data Structures path.