📚 Table of Contents
📋 Problem Statement
Given m x n board and word, return true if you can
build the word using sequentially adjacent cells (up/down/left/right), without reusing a
cell in the same path.
Examples
board=[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word="ABCCED"Output: true
word="ABCB" on same board -> false
🎯 Real-World Analogy
Treasure Hunt on a Letter Grid
You follow a clue string across a map. At each step you can move only to neighboring squares. If a route fails, you backtrack and try another route.
💡 Key Insights
- This is path existence in a grid with visited-state constraints.
- DFS naturally models trying one route then backtracking.
- Mark cells visited in current path only, then restore on unwind.
- Early mismatch checks prune search aggressively.
💻 Solution Approaches
Approach 1: BFS Over Path States
Time: Exponential | Space: High state overhead
Possible but cumbersome due to storing visited sets per path state.
Approach 2: DFS + Backtracking (Recommended)
Time: O(M * N * 4^L) worst case | Space: O(L) recursion depth
Python Implementation
from typing import List
def exist(board: List[List[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def dfs(r: int, c: int, idx: int) -> bool:
if idx == len(word):
return True
if r < 0 or r >= rows or c < 0 or c >= cols:
return False
if board[r][c] != word[idx]:
return False
temp = board[r][c]
board[r][c] = '#'
found = (
dfs(r + 1, c, idx + 1)
or dfs(r - 1, c, idx + 1)
or dfs(r, c + 1, idx + 1)
or dfs(r, c - 1, idx + 1)
)
board[r][c] = temp
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
JavaScript Implementation
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
function dfs(r, c, idx) {
if (idx === word.length) return true;
if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
if (board[r][c] !== word[idx]) return false;
const temp = board[r][c];
board[r][c] = '#';
const found =
dfs(r + 1, c, idx + 1) ||
dfs(r - 1, c, idx + 1) ||
dfs(r, c + 1, idx + 1) ||
dfs(r, c - 1, idx + 1);
board[r][c] = temp;
return found;
}
for (let r = 0; r < rows; r += 1) {
for (let c = 0; c < cols; c += 1) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}
🔍 Step-by-Step Walkthrough
For word "ABCCED":
⚡ Complexity Analysis
Time: O(M * N * 4^L) worst case where L is word length. Branching reduces after first move because revisits are blocked.
Space: O(L) recursion stack depth in the active path.
🔧 Edge Cases
- Single-cell board and one-letter word.
- Word longer than total cells -> impossible.
- Repeated letters causing revisit temptations.
- Word absent despite matching prefix paths.
🧪 Test Cases
Python
def test_exist():
board = [
["A", "B", "C", "E"],
["S", "F", "C", "S"],
["A", "D", "E", "E"],
]
assert exist([row[:] for row in board], "ABCCED") is True
assert exist([row[:] for row in board], "SEE") is True
assert exist([row[:] for row in board], "ABCB") is False
print("all tests passed")JavaScript
function cloneBoard(board) {
return board.map((row) => [...row]);
}
function testExist() {
const board = [
["A", "B", "C", "E"],
["S", "F", "C", "S"],
["A", "D", "E", "E"],
];
console.assert(exist(cloneBoard(board), "ABCCED") === true, "test 1");
console.assert(exist(cloneBoard(board), "SEE") === true, "test 2");
console.assert(exist(cloneBoard(board), "ABCB") === false, "test 3");
console.log("all tests passed");
}💼 Interview Tips
- State DFS + backtracking before coding details.
- Explain why visited marks must be reverted after recursion.
- Mention pruning opportunities (char frequency precheck).
- Be explicit that diagonal movement is not allowed.
🎓 Key Takeaways
- Word Search is classic DFS backtracking with path-local visited state.
- Restoring board state is essential for exploring alternate branches.
- Pruning strategy often decides whether solutions pass time limits.