Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells (horizontally or vertically adjacent). The same letter cell may not be used more than once.
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" → Output: trueInput: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" → Output: true
DFS with backtracking: for each cell matching word[0], start a DFS. Mark cells as visited by temporarily changing the character. If all characters match, return true; otherwise restore the cell and try other paths.
- For each cell (r, c) where board[r][c] == word[0], call dfs(r, c, 0).
- In dfs: if idx == word.length, return true.
- Mark board[r][c] = '#' to avoid reuse, then explore 4 neighbors.
- Restore board[r][c] after recursive calls (backtrack).
class Solution {
public boolean exist(char[][] board, String word) {
int m = board.length, n = board[0].length;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (dfs(board, word, r, c, 0)) return true;
return false;
}
private boolean dfs(char[][] board, String word, int r, int c, int idx) {
if (idx == word.length()) return true;
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return false;
if (board[r][c] != word.charAt(idx)) return false;
char tmp = board[r][c];
board[r][c] = '#';
boolean found = dfs(board, word, r+1, c, idx+1) ||
dfs(board, word, r-1, c, idx+1) ||
dfs(board, word, r, c+1, idx+1) ||
dfs(board, word, r, c-1, idx+1);
board[r][c] = tmp;
return found;
}
}
- Time Complexity: O(M*N * 4^L) where L is word length
- Space Complexity: O(L) — recursion depth