The problem. Given an m × n grid of letters board and a string word, return true if the word can be spelled by a path of adjacent cells (up, down, left or right). The same cell may not be used twice in one word.
board = [["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]]
word = "ABCCED" -> true
word = "SEE" -> true
word = "ABCB" -> false (the B can't be used twice)The last chapter backtracks over positions on a grid or board instead of items in a list: the next letter of a word in a neighbouring cell, a queen in the next row, a digit in the next empty square. The template is the same — choose, explore, un-choose — and the board itself records the choices (mark a cell, place a queen, write a digit) so un-choosing means restoring the board. Strong pruning is what makes these hard problems run fast.
Try every cell as the start. From a cell holding word[i], look for word[i + 1] in its four neighbours. To stop a path from reusing a cell, mark it (overwrite it with #) while it's on the path, and restore it when backing out — that's the un-choose step. The search stops as soon as the whole word is matched.
The path grows into neighbours holding the next letter; cells on the path are marked so they can't be reused.
function exist(board, word) { const m = board.length, n = board[0].length; const dfs = (r, c, i) => { if (i === word.length) return true; // every letter matched if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[i]) return false; const saved = board[r][c]; board[r][c] = "#"; // mark: on the current path 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] = saved; // un-mark when backing out return found; }; for (let r = 0; r < m; r++) { for (let c = 0; c < n; c++) if (dfs(r, c, 0)) return true; } return false;}Time O(m · n · 3ᴸ) for a word of length L: every start cell, then at most 3 new directions per step (the fourth is where you came from). Space O(L) for the call stack; marking in place needs no visited array.
Two cheap checks often decide the answer — or shrink the search — before any DFS: if the board doesn't contain enough of some letter, return false at once; and if the word's last letter is rarer on the board than its first, search for the reversed word, so far fewer starting cells match.
function exist(board, word) { const m = board.length, n = board[0].length; const count = new Map(); for (const row of board) for (const ch of row) count.set(ch, (count.get(ch) ?? 0) + 1); const need = new Map(); for (const ch of word) need.set(ch, (need.get(ch) ?? 0) + 1); for (const [ch, k] of need) if ((count.get(ch) ?? 0) < k) return false; // not enough letters if ((count.get(word[0]) ?? 0) > (count.get(word[word.length - 1]) ?? 0)) { word = [...word].reverse().join(""); // start from the rarer end } const dfs = (r, c, i) => { if (i === word.length) return true; if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] !== word[i]) return false; const saved = 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] = saved; return found; }; for (let r = 0; r < m; r++) { for (let c = 0; c < n; c++) if (dfs(r, c, 0)) return true; } return false;}Same worst case, but these two checks turn the classic slow test cases — a board full of A's and a word of A's ending in B — from seconds into microseconds.
"ABCB" must fail; forgetting to mark lets the path step back onto B.[["a"]] with "a" (true) and "b" (false).