Word Search
Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same cell may not be used more than once in one word. Use backtracking that steps into a matching neighbor, temporarily marks that cell visited so the same path can't reuse it, and undoes the mark on the way back out so a different path can use that cell.
Constraints
- m == board.length
- n == boardi.length
- 1 ≤ m, n ≤ 6
- 1 ≤ word.length ≤ 15
- board and word consist of only lowercase and uppercase English letters
Example
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"trueExplanation Starting at the top-left A, the path A → B → C → C → E → D visits six adjacent cells in order without reusing any of them.
In plain terms
- Adjacent
- Directly next to a cell — up, down, left, or right, but never diagonally.
Step into a matching neighbor, mark it visited, undo on the way back out
Start at (0,0)="A", matches word[0]. Mark visited, look for "B" next.
What happens in this step
path so far: (0,0)='A' call: backtrack(0, 0, 0) board[0][0]='A' matches word[0]='A'. The cell is temporarily marked '#' (visited) and backtrack tries its neighbors in order down, up, right, left, looking for word[1]='B'.
Steps to visualize
- Start a search from every cell that matches the first letter of the word.
- If the current cell matches the next letter, mark it visited and try each of its unvisited neighbors for the letter after that.
- If a mismatch or a dead end is hit, undo the visited mark on this cell and report failure up to the caller.
- The word is found the moment every letter has been matched along one connected path.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Start at (0,0)="A", matches word[0]. Mark visited, look for "B" next.
What happens in this step
path so far: (0,0)='A' call: backtrack(0, 0, 0) board[0][0]='A' matches word[0]='A'. The cell is temporarily marked '#' (visited) and backtrack tries its neighbors in order down, up, right, left, looking for word[1]='B'.
Solution
function exist(board, word) {
const rows = board.length;
const cols = board[0].length;
function backtrack(row, col, index) {
if (index === word.length) {
return true;
}
if (row < 0 || row >= rows || col < 0 || col >= cols) {
return false;
}
if (board[row][col] !== word[index]) {
return false;
}
const temp = board[row][col];
board[row][col] = '#';
const found =
backtrack(row + 1, col, index + 1) ||
backtrack(row - 1, col, index + 1) ||
backtrack(row, col + 1, index + 1) ||
backtrack(row, col - 1, index + 1);
board[row][col] = temp;
return found;
}
for (let row = 0; row < rows; row++) {
for (let col = 0; col < cols; col++) {
if (backtrack(row, col, 0)) {
return true;
}
}
}
return false;
}- Time
- O(m · n · 4^L)
- Space
- O(L)
Test cases
| Input | Expected | Covers |
|---|---|---|
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" | true | example from the docstring |
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" | true | a shorter word found along a different path |
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" | false | the only path would need to reuse a cell, which is not allowed |
board = [["a"]], word = "a" | true | smallest valid board, a single matching cell |
board = [["a"]], word = "b" | false | smallest board, no match at all |
board = [["a","a"]], word = "aa" | true | two adjacent identical letters form the word |
board = [["a","b"],["c","d"]], word = "abcd" | false | letters exist on the board but no adjacent path connects them in order |