Word Search
Receives a rectangular grid of single letters and a target word, and returns whether the word can be traced through the grid by moving to horizontally or vertically adjacent cells, never reusing the same cell twice within one trace. From every cell it tries a depth-first search that matches the word letter by letter, marking each cell used along the current path and unmarking it (backtracking) whenever a path dead-ends, so a failed attempt never blocks a different starting cell or direction from reusing that cell. Returns true as soon as one full trace matches the word; returns false only after every starting cell and every direction has been exhausted. An empty word is trivially found (true); an empty grid cannot contain any word (false).
Visualization
- Input
- Result
Algorithm code
// Word Search — a single pure function. Receives a rectangular grid of
// single-letter strings and a target word, and returns whether the word can
// be traced through the grid by moving to horizontally or vertically
// adjacent cells, never reusing the same cell twice within one trace.
/**
* @param {string[]} grid - rows of equal-length strings, one letter per cell
* @param {string} word - the word to search for
* @returns {boolean} true if the word can be traced through the grid
*/
export function wordSearch(grid, word) {
if (word.length === 0) {
return true;
}
if (grid.length === 0 || grid[0].length === 0) {
return false;
}
const rows = grid.length;
const cols = grid[0].length;
const visited = grid.map((row) => row.split("").map(() => false));
function dfs(row, col, index) {
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return false;
}
if (visited[row][col] || grid[row][col] !== word[index]) {
return false;
}
visited[row][col] = true;
if (index === word.length - 1) {
return true;
}
const found =
dfs(row + 1, col, index + 1) ||
dfs(row - 1, col, index + 1) ||
dfs(row, col + 1, index + 1) ||
dfs(row, col - 1, index + 1);
if (!found) {
visited[row][col] = false;
}
return found;
}
for (let row = 0; row < rows; row += 1) {
for (let col = 0; col < cols; col += 1) {
if (dfs(row, col, 0)) {
return true;
}
}
}
return false;
}FUNCTION wordSearch(grid, word):
IF length(word) = 0:
RETURN true
IF length(grid) = 0 OR length(grid[0]) = 0:
RETURN false
rows ← length(grid)
cols ← length(grid[0])
visited ← rows × cols array of false
FUNCTION dfs(row, col, index):
IF row < 0 OR row ≥ rows OR col < 0 OR col ≥ cols:
RETURN false
IF visited[row][col] OR grid[row][col] ≠ word[index]:
RETURN false
visited[row][col] ← true
IF index = length(word) - 1:
RETURN true
found ← dfs(row + 1, col, index + 1)
OR dfs(row - 1, col, index + 1)
OR dfs(row, col + 1, index + 1)
OR dfs(row, col - 1, index + 1)
IF NOT found:
visited[row][col] ← false
RETURN found
FOR row FROM 0 TO rows - 1:
FOR col FROM 0 TO cols - 1:
IF dfs(row, col, 0):
RETURN true
RETURN false