76. Word Search

From each cell matching the first letter, DFS to see if the word can be spelled by visiting adjacent unvisited cells.

Approach

1. For each cell matching word[0], start DFS.
2. Mark cell as visited, try all 4 directions for the next character.
3. Backtrack (unmark) if no path found.
4. Return true on first successful path.

Complexity

• Time: O(mn3^L) where L is word length
• Space: O(L) recursion stack

class Solution {
    public boolean exist(char[][] board, String word) {
        int rows = board.length, cols = board[0].length;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (dfs(board, word, r, c, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, String word, int r, int c, int i) {
        if (i == word.length()) return true;
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != word.charAt(i)) return false;
        char temp = board[r][c];
        board[r][c] = '#';
        boolean found = dfs(board, word, r + 1, c, i + 1)
                      || dfs(board, word, r - 1, c, i + 1)
                      || dfs(board, word, r, c + 1, i + 1)
                      || dfs(board, word, r, c - 1, i + 1);
        board[r][c] = temp;
        return found;
    }
}