Word Search
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
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.