Given a 2D board of characters, determine whether a target word can be spelled by following a path of adjacent cells (up/down/left/right, no reuse). The key is a clean backtracking DFS — borrow each cell by temporarily marking it visited, recurse into all four neighbours, and restore on the way out.
Given an m×n grid of characters and a string word, return true if the word exists in the grid spelled out along a path of horizontally/vertically adjacent cells, where each cell may be used at most once. Example: board = ["ABCE","SFCS","ADEE"], word = "ABCCED" → true (the path goes A→B→C→C→E→D).
'#') so future calls in the same branch can't visit it again. After all four recursive calls return, restore the original character — this lets completely independent starting paths reuse every cell freely.(r,c); call dfs(r, c, 0) whenever board[r][c] === word[0].depth === word.length, we consumed all characters — return true.false immediately.tmp = board[r][c], write board[r][c] = '#' to block revisits within this path.dfs for all four neighbours with depth + 1. If any returns true, restore and propagate true.board[r][c] = tmp — the cell is available again for other branches.dfs.Space is O(L) for the recursion stack (depth bounded by word length). In the worst case every cell matches and we still try every path, but in practice early mismatch prunes the tree aggressively.
3×4 board for "ABCCED". Try each cell as a starting point; backtrack on mismatch.function exist(board: string[][], word: string): boolean {
const R = board.length;
const C = board[0].length;
const DIRS: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
function dfs(r: number, c: number, depth: number): boolean {
if (depth === word.length) return true;
if (r < 0 || r >= R || c < 0 || c >= C) return false;
if (board[r][c] !== word[depth]) return false;
const tmp = board[r][c];
board[r][c] = '#'; // mark visited
for (const [dr, dc] of DIRS) {
if (dfs(r + dr, c + dc, depth + 1)) {
board[r][c] = tmp; // restore before returning
return true;
}
}
board[r][c] = tmp; // backtrack
return false;
}
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (dfs(r, c, 0)) return true;
}
}
return false;
}tmp, then overwrite with '#'. Because the character check is done above, any future call into this cell during the same DFS path will see '#' and fail the match check — no extra visited set needed.true, restore tmp before propagating — the board must be clean for the caller.tmp back so the cell is reusable by entirely different starting paths in the outer loops.dfs from every cell. The first true bubbles up immediately thanks to the early-return on success; otherwise return false after exhausting all starts.visited: boolean[][]array (same O(R × C) space). The borrow/restore pattern is usually preferred for its elegance and lower constant.DIRS from 4 to 8 entries; complexity becomes O(R × C × 7L).word.length > R * C, return false immediately — there aren't enough cells to spell it without reuse.| "word exists in grid / adjacent path" | backtracking DFS + cell borrow |
| "each cell used at most once" | overwrite with sentinel, restore after recurse |
| "find any valid arrangement on shared state" | backtrack: mutate → recurse → undo |
| "all words from dictionary in grid" | Trie + backtracking DFS (Word Search II) |
function exist(board: string[][], word: string): boolean {
const R = board.length, C = board[0].length;
const DIRS: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
function dfs(r: number, c: number, depth: number): boolean {
if (depth === word.length) return true;
if (r < 0 || r >= R || c < 0 || c >= C) return false;
if (board[r][c] !== word[depth]) return false;
const tmp = board[r][c];
board[r][c] = '#';
for (const [dr, dc] of DIRS) {
if (dfs(r + dr, c + dc, depth + 1)) { board[r][c] = tmp; return true; }
}
board[r][c] = tmp;
return false;
}
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++)
if (dfs(r, c, 0)) return true;
return false;
}["ABCE","SFCS","ADEE"] and word = "ABCCED", what does the algorithm return?dfs(r, c, depth) and board[r][c] !== word[depth], the correct action is: