Word Search

Find a word hidden in a grid of letters, moving between side-by-side cells without reusing one.

The idea

Try every cell as a starting point for the first letter. From a matching cell, mark it so it cannot be reused, then check its four neighbours for the next letter. If every neighbour fails, unmark the cell and let the caller try a different one.

Code

public static bool 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;
}

static bool Dfs(char[][] board, string word, int r, int c, int i) {
    if (i == word.Length) return true;
    if (r < 0 || c < 0 || r >= board.Length || c >= board[0].Length) return false;
    if (board[r][c] != word[i]) return false;
    char saved = board[r][c];
    board[r][c] = '#'; // mark visited
    bool 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] = saved; // backtrack
    return found;
}

Tips

• Overwriting the cell with '#' is a cheap visited check: a cell in the current path can never equal a letter, so the mismatch check in Dfs also rejects revisits for free.
• Restoring the saved character after the recursive calls return is what makes the next starting cell or branch see the original board again.

In the .NET library

Mutating the board in place avoids a separate bool[,] visited array, but only works because the change is always undone before the function returns. Forgetting the restore line is a classic bug: later searches would see a board full of '#'.