Word Search
MediumBacktracking
You get a board of letters and a word. Return true if the word can be spelled by a path through the board, and false otherwise.
Each step of the path moves to a cell up, down, left or right of the last one, and a path may not use the same cell twice. On this page the board is written as an array of rows, top row first, each cell a one-letter string. Upper and lower case are different letters.
Examples
Input: board = [["c", "a", "t"], ["x", "r", "s"], ["d", "o", "g"]], word = "cars" Output: true
c at the top left, right to a, down to r, right to s.
Input: board = [["c", "a", "t"], ["x", "r", "s"], ["d", "o", "g"]], word = "cog" Output: false
The only c has a and x beside it, never an o.
Constraints
1 ≤ m, n ≤ 6for a board of m rows and n columns1 ≤ word.length ≤ 15- The board and the word use English letters, upper and lower case.
Stuck?
Hint 1
Try every cell as the start. From a cell that matches the next letter, try each of its four neighbors for the letter after it: a depth-first search with backtracking.
Hint 2
Mark a cell as used while it is on the current path, and unmark it when you step back off it, so another path can still use it.
The idea
Try every cell as the start and grow the path one matching letter at a time, in all four directions. A path may not use a cell twice, so mark a cell while it is on the path, and clear the mark when the search backs off it so other paths can still use it.
Time O(m · n · 3^L) for a word of length LExtra space O(L) for the recursion
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
walk asks whether the word from position i on can be spelled starting at row r, column c. Once i passes the last letter, every letter has matched. This test comes first because the call after the last letter may be off the grid, and it must still count as found.
function exist(board, word) { const rows = board.length; const cols = board[0].length; const walk = (r, c, i) => { if (i === word.length) return true; if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) return false; const letter = board[r][c]; board[r][c] = '#'; const found = walk(r + 1, c, i + 1) || walk(r - 1, c, i + 1) || walk(r, c + 1, i + 1) || walk(r, c - 1, i + 1); board[r][c] = letter; return found; }; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (walk(r, c, 0)) return true; } } return false;}The trap
This version checks each letter but never marks a cell as used. Every step still lands on the right letter, so the paths it finds look valid. But a path can step back onto the cell it came from. A word whose letters go back and forth between two neighbouring cells is then reported found, even when the board holds one of those letters only once.
function exist(board, word) { const rows = board.length; const cols = board[0].length; const walk = (r, c, i) => { if (i === word.length) return true; if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) return false; // never marks the cell as used, so a path can come back through it return walk(r + 1, c, i + 1) || walk(r - 1, c, i + 1) || walk(r, c + 1, i + 1) || walk(r, c - 1, i + 1); }; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (walk(r, c, 0)) return true; } } return false;}