Problem
Given an m×n grid of characters and a word, return true if the word exists in the grid by traversing adjacent cells (no reuse).
Example
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: trueSolution
DFS from each cell. Mark visited cells with a temp marker; restore after recursion.
def exist(board, word):
rows, cols = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word): return True
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]: return False
temp = board[r][c]
board[r][c] = '#'
found = dfs(r+1,c,i+1) or dfs(r-1,c,i+1) or dfs(r,c+1,i+1) or dfs(r,c-1,i+1)
board[r][c] = temp
return found
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0): return True
return Falsefunction exist(board, word) {
const rows = board.length, cols = board[0].length;
function dfs(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 temp = 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] = temp;
return found;
}
for (let r = 0; r < rows; r++)
for (let c = 0; c < cols; c++)
if (dfs(r, c, 0)) return true;
return false;
}bool dfs(vector<vector<char>>& b, string& w, int r, int c, int i) {
if (i == w.size()) return true;
if (r < 0 || r >= b.size() || c < 0 || c >= b[0].size() || b[r][c] != w[i]) return false;
char temp = b[r][c]; b[r][c] = '#';
bool found = dfs(b,w,r+1,c,i+1) || dfs(b,w,r-1,c,i+1) || dfs(b,w,r,c+1,i+1) || dfs(b,w,r,c-1,i+1);
b[r][c] = temp;
return found;
}
bool exist(vector<vector<char>>& board, string word) {
for (int r = 0; r < board.size(); r++)
for (int c = 0; c < board[0].size(); c++)
if (dfs(board, word, r, c, 0)) return true;
return false;
}public boolean exist(char[][] board, String word) {
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
if (dfs(board, word, r, c, 0)) return true;
return false;
}
private boolean dfs(char[][] b, String w, int r, int c, int i) {
if (i == w.length()) return true;
if (r < 0 || r >= b.length || c < 0 || c >= b[0].length || b[r][c] != w.charAt(i)) return false;
char temp = b[r][c]; b[r][c] = '#';
boolean found = dfs(b,w,r+1,c,i+1) || dfs(b,w,r-1,c,i+1) || dfs(b,w,r,c+1,i+1) || dfs(b,w,r,c-1,i+1);
b[r][c] = temp;
return found;
}Complexity
- Time: O(m * n * 4^L)
- Space: O(L)
Explanation
L is the word length. The temporary marker (#) prevents revisiting cells during a single search path. We restore on backtrack.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?