Backtracking
Intuition
We try to build the word character by character starting from every cell in the grid. From each cell, we explore all four directions using backtracking. At each step, we check if the current cell matches the expected character in the word. If it does, we mark the cell as visited (to prevent reuse) and recurse to find the next character. If the recursion leads to a dead end, we unmark the cell (backtrack) and try other directions. The search succeeds if we match all characters in the word. We fail early if the current cell does not match or is out of bounds.
Algorithm
- Iterate through every cell in the grid as a potential starting position.
- For each starting cell, call the backtracking function with the first character index.
- In the backtracking function, check if the index equals the word length -- if so, we found the word, return true.
- Check bounds, whether the cell matches the current character, and whether it is already visited.
- Mark the cell as visited by replacing its value with a sentinel character.
- Recursively try all four adjacent cells with the next character index.
- Restore the cell's original value (backtrack) and return the result.
Time
O(m * n * 3^L) where L is the word length, since each cell branches into at most 3 directions (excluding where we came from)SpaceO(L) for the recursion stack depthCode (C++ · Java · Python · Go)
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (backtrack(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private:
bool backtrack(vector<vector<char>>& board, string& word, int r, int c, int idx) {
if (idx == word.size()) return true;
int m = board.size(), n = board[0].size();
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word[idx]) {
return false;
}
char temp = board[r][c];
board[r][c] = '#';
bool found = backtrack(board, word, r + 1, c, idx + 1)
|| backtrack(board, word, r - 1, c, idx + 1)
|| backtrack(board, word, r, c + 1, idx + 1)
|| backtrack(board, word, r, c - 1, idx + 1);
board[r][c] = temp;
return found;
}
};class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (backtrack(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean backtrack(char[][] board, String word, int r, int c, int idx) {
if (idx == word.length()) return true;
int m = board.length, n = board[0].length;
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(idx)) {
return false;
}
char temp = board[r][c];
board[r][c] = '#';
boolean found = backtrack(board, word, r + 1, c, idx + 1)
|| backtrack(board, word, r - 1, c, idx + 1)
|| backtrack(board, word, r, c + 1, idx + 1)
|| backtrack(board, word, r, c - 1, idx + 1);
board[r][c] = temp;
return found;
}
}from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def backtrack(r, c, idx):
if idx == len(word):
return True
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[idx]:
return False
temp = board[r][c]
board[r][c] = '#'
found = (backtrack(r + 1, c, idx + 1)
or backtrack(r - 1, c, idx + 1)
or backtrack(r, c + 1, idx + 1)
or backtrack(r, c - 1, idx + 1))
board[r][c] = temp
return found
for i in range(m):
for j in range(n):
if backtrack(i, j, 0):
return True
return Falsefunc exist(board [][]byte, word string) bool {
m, n := len(board), len(board[0])
var backtrack func(r, c, idx int) bool
backtrack = func(r, c, idx int) bool {
if idx == len(word) {
return true
}
if r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word[idx] {
return false
}
temp := board[r][c]
board[r][c] = '#'
found := backtrack(r+1, c, idx+1) ||
backtrack(r-1, c, idx+1) ||
backtrack(r, c+1, idx+1) ||
backtrack(r, c-1, idx+1)
board[r][c] = temp
return found
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if backtrack(i, j, 0) {
return true
}
}
}
return false
}