The DFS
boolean exists(char[][] board, String word) {
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
if (dfs(board, r, c, word, 0)) return true;
return false;
}
boolean dfs(char[][] board, int r, int c, String word, int idx) {
if (idx == word.length()) return true;
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
|| board[r][c] != word.charAt(idx)) return false;
char tmp = board[r][c];
board[r][c] = '#'; // mark visited
boolean found = dfs(board, r+1, c, word, idx+1) || dfs(board, r-1, c, word, idx+1)
|| dfs(board, r, c+1, word, idx+1) || dfs(board, r, c-1, word, idx+1);
board[r][c] = tmp; // restore
return found;
}Advertisement
Marking + restoring
Overwrite cell during DFS to avoid revisiting. Restore on backtrack.
Advertisement
The DFS
boolean exists(char[][] board, String word) {
for (int r = 0; r < board.length; r++)
for (int c = 0; c < board[0].length; c++)
if (dfs(board, r, c, word, 0)) return true;
return false;
}
boolean dfs(char[][] board, int r, int c, String word, int idx) {
if (idx == word.length()) return true;
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length
|| board[r][c] != word.charAt(idx)) return false;
char tmp = board[r][c];
board[r][c] = '#'; // mark visited
boolean found = dfs(board, r+1, c, word, idx+1) || dfs(board, r-1, c, word, idx+1)
|| dfs(board, r, c+1, word, idx+1) || dfs(board, r, c-1, word, idx+1);
board[r][c] = tmp; // restore
return found;
}Marking + restoring
Overwrite cell during DFS to avoid revisiting. Restore on backtrack.
Complexity
O(m × n × 4^L) where L is word length. Pruning stops most branches early.
Multi-word extension
Word Search II: many words to find. Build trie of words. Single DFS pass through grid + trie.