Word Search
Problem
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.
Try every cell as a starting point. From there, DFS: if the current letter matches word[k], mark the cell visited (overwrite with '#'), recurse into the four neighbours with k + 1, restore the letter on unwind, and short-circuit on success. Reaching k == len(word) means the trace is complete.
grid = [[A,B,C,E],[S,F,C,S],[A,D,E,E]], word = "ABCCED"truedef exist(grid, word):
R, C = len(grid), len(grid[0])
def dfs(r, c, k):
if k == len(word): return True
if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != word[k]:
return False
ch = grid[r][c]; grid[r][c] = "#"
ok = (dfs(r + 1, c, k + 1) or dfs(r - 1, c, k + 1)
or dfs(r, c + 1, k + 1) or dfs(r, c - 1, k + 1))
grid[r][c] = ch
return ok
for r in range(R):
for c in range(C):
if dfs(r, c, 0): return True
return Falsefunction exist(grid, word) {
const R = grid.length, C = grid[0].length;
function dfs(r, c, k) {
if (k === word.length) return true;
if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] !== word[k]) return false;
const ch = grid[r][c]; grid[r][c] = "#";
const ok = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1)
|| dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
grid[r][c] = ch;
return ok;
}
for (let r = 0; r < R; r++)
for (let c = 0; c < C; c++)
if (dfs(r, c, 0)) return true;
return false;
}char[][] g; String w; int R, C;
public boolean exist(char[][] grid, String word) {
g = grid; w = word; R = grid.length; C = grid[0].length;
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (dfs(r, c, 0)) return true;
return false;
}
boolean dfs(int r, int c, int k) {
if (k == w.length()) return true;
if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] != w.charAt(k)) return false;
char ch = g[r][c]; g[r][c] = '#';
boolean ok = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1)
|| dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);
g[r][c] = ch;
return ok;
}int R, C;
bool dfs(vector<vector<char>>& g, string& w, int r, int c, int k) {
if (k == (int)w.size()) return true;
if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] != w[k]) return false;
char ch = g[r][c]; g[r][c] = '#';
bool ok = dfs(g, w, r + 1, c, k + 1) || dfs(g, w, r - 1, c, k + 1)
|| dfs(g, w, r, c + 1, k + 1) || dfs(g, w, r, c - 1, k + 1);
g[r][c] = ch;
return ok;
}
bool exist(vector<vector<char>>& g, string w) {
R = g.size(); C = g[0].size();
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (dfs(g, w, r, c, 0)) return true;
return false;
}Explanation
We're checking whether a word can be traced through the grid by stepping between neighbouring cells, never reusing a cell. The approach is a depth-first search that tries to match the word one letter at a time, with backtracking to recover when a path dead-ends.
Because the word could start anywhere, we launch a DFS from every cell. The dfs(r, c, k) function asks: "can I match word[k] onward starting at cell (r, c)?"
Inside, it fails fast if we step out of bounds or the cell's letter doesn't equal word[k]. If it matches, we mark the cell visited by overwriting it with '#' so the same path can't reuse it, then recurse into the four neighbours with k + 1.
The backtracking step is restoring the original letter (grid[r][c] = ch) after exploring, so the cell is free for other paths. We short-circuit on the first success: reaching k == len(word) means the whole word was traced, so it returns true.
Example: for "ABCCED" the search finds the trail (0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1), matching every letter in order, so the answer is true.