Word Search: the idea to remember.

The core insight

Try every starting cell. Match the next character, mark the cell during recursion, then restore it on return.

Why it works

The recursion explores exactly the simple grid paths matching the word prefix. Restoring allows independent candidate paths to reuse cells.

The mistake to avoid

Always restore the board, including after a successful branch. The temporary marker assumes alphabetic board cells.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

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

Make the next connection