Approach Summary
DFS from every cell. Mark cell as visited by temporarily changing its value. Restore on backtrack.
Full Solution & Approach
Try starting the word at every cell, and from each cell explore in the four directions with DFS. The visited state is handled by temporarily replacing the current cell with a sentinel (e.g. "#") before recursing and restoring it afterward — this marks the path without a separate visited matrix and prevents revisiting cells on the current path. Match characters position by position: when a cell equals word[k], recurse with k + 1 into valid neighbors. The recursion succeeds when k equals the word length, and fails (backtracks) when a cell does not match or goes out of bounds. The sentinel-restore trick is what makes backtracking on a grid clean — it also prevents the same letter cell from being used twice in one path, which the problem explicitly forbids.
Worst case explores 4 directions to depth L from every cell — O(m × n × 4^L) time. Recursion depth equals the word length plus the grid dimensions — O(L) space.
Solution Code
Solution
def exist(board: list[list[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def dfs(i: int, j: int, k: int) -> bool:
if k == len(word):
return True
if not (0 <= i < m and 0 <= j < n) or board[i][j] != word[k]:
return False
board[i][j] = '#'
found = (
dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or
dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
)
board[i][j] = word[k]
return found
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return Falsefunction exist(board, word) {
const m = board.length, n = board[0].length;
function dfs(i, j, k) {
if (k === word.length) return true;
if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== word[k]) return false;
const tmp = board[i][j];
board[i][j] = '#';
const found = dfs(i + 1, j, k + 1) || dfs(i - 1, j, k + 1) ||
dfs(i, j + 1, k + 1) || dfs(i, j - 1, k + 1);
board[i][j] = tmp;
return found;
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (dfs(i, j, 0)) return true;
}
}
return false;
}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 (dfs(board, i, j, word, 0)) return true;
}
}
return false;
}
private boolean dfs(char[][] board, int i, int j, String word, int k) {
if (k == word.length()) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) {
return false;
}
board[i][j] = '#';
boolean found = dfs(board, i + 1, j, word, k + 1)
|| dfs(board, i - 1, j, word, k + 1)
|| dfs(board, i, j + 1, word, k + 1)
|| dfs(board, i, j - 1, word, k + 1);
board[i][j] = word.charAt(k);
return found;
}bool exist(vector<vector<char>>& board, const 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 (dfs(board, i, j, word, 0)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>>& board, int i, int j, const string& word, int k) {
if (k == (int)word.size()) return true;
if (i < 0 || i >= (int)board.size() || j < 0 || j >= (int)board[0].size() || board[i][j] != word[k]) {
return false;
}
board[i][j] = '#';
bool found = dfs(board, i + 1, j, word, k + 1)
|| dfs(board, i - 1, j, word, k + 1)
|| dfs(board, i, j + 1, word, k + 1)
|| dfs(board, i, j - 1, word, k + 1);
board[i][j] = word[k];
return found;
}Edge Cases to Watch
- Word longer than the grid has cells — impossible
- Single-letter word — matches any cell with that letter
- The word may turn and reuse neighbors — the sentinel prevents same-cell reuse on one path
- Letters present but not connected — false
How to Recognize This Pattern
- Find word path in grid
- Mark-and-restore visited cells
Complexity Analysis
Time Complexity
O(m × n × 4^L)
Space Complexity
O(L)