Word Search

Medium

Problem

Return true if the word can be spelled in the grid by a path of adjacent cells (up, down, left or right), using each cell at most once.

Example 1

Input:  board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2

Input:  same board, word = "ABCB"
Output: false

Test cases

Case 1

Input:    [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED"
Expected: true

Case 2

Input:    [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"
Expected: true

Case 3

Input:    [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCB"
Expected: false

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DFS with in-place visited marking

Time O(R·C·3^L)Space O(L)

Start from each cell matching word[0]; mark the cell, try four neighbours for the next char, and restore it on return.

function exist(board, word) {
const R = board.length, C = board[0].length;
const dfs = (r, c, i) => {
if (i === word.length) return true;
if (r < 0 || c < 0 || r >= R || c >= C || board[r][c] !== word[i]) return false;
const ch = board[r][c];
board[r][c] = '#';
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] = ch;
return found;
};
for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (dfs(r, c, 0)) return true;
return false;
}

Pruning: return false early if the board lacks enough of some letter in the word.