Word Search and Sudoku Solver

Word Search (LeetCode 79)

Given a 2D grid of characters and a string word, find if the word exists in the grid using only adjacent cells (up, down, left, right).

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

private boolean dfs(char[][] board, String word, int k, int i, int j) {
    if (k == word.length()) return true;
    if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) {
        return false;
    }
    
    char temp = board[i][j];
    board[i][j] = '#'; // Mark as visited for this recursive path
    
    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    for (int[] d : directions) {
        if (dfs(board, word, k + 1, i + d[0], j + d[1])) {
            board[i][j] = temp; // Restore before returning true
            return true;
        }
    }
    
    board[i][j] = temp; // Backtrack: Restore the original character
    return false;
}

Word Search II (LeetCode 212)

Finding multiple words in a grid simultaneously.

Optimization: Use a Trie (Prefix Tree) to store all target words. Instead of searching each word individually, we traverse the grid once and check if the current path forms any word in the Trie.

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word; // Stores the full word at the leaf node
}

public List<String> findWords(char[][] board, String[] words) {
    TrieNode root = buildTrie(words);
    List<String> result = new ArrayList<>();
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            dfs(board, i, j, root, result);
        }
    }
    return result;
}

private void dfs(char[][] board, int i, int j, TrieNode node, List<String> result) {
    char c = board[i][j];
    if (c == '#' || node.children[c - 'a'] == null) return;
    
    node = node.children[c - 'a'];
    if (node.word != null) {
        result.add(node.word);
        node.word = null; // Prevent duplicate entries
    }
    
    board[i][j] = '#';
    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    for (int[] d : directions) {
        int ni = i + d[0], nj = j + d[1];
        if (ni >= 0 && ni < board.length && nj >= 0 && nj < board[0].length) {
            dfs(board, ni, nj, node, result);
        }
    }
    board[i][j] = c;
}

Sudoku Solver (LeetCode 37)

Fill an $9 \times 9$ Sudoku board.

public void solveSudoku(char[][] board) {
    solve(board);
}

private boolean solve(char[][] board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') continue;
            
            for (char c = '1'; c <= '9'; c++) {
                if (isValid(board, i, j, c)) {
                    board[i][j] = c;
                    if (solve(board)) return true;
                    board[i][j] = '.'; // Backtrack
                }
            }
            return false; // No digit from 1-9 is valid, trigger backtrack at caller
        }
    }
    return true; // Puzzle complete
}

private boolean isValid(char[][] board, int row, int col, char c) {
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == c) return false; // Duplicate in row
        if (board[i][col] == c) return false; // Duplicate in column
        // Duplicate in 3x3 block
        int br = 3 * (row / 3) + i / 3;
        int bc = 3 * (col / 3) + i % 3;
        if (board[br][bc] == c) return false;
    }
    return true;
}

Advanced Optimization Tip: Implement the "Most Constrained Variable First" heuristic. Find the empty cell with the fewest possible legal candidates and fill it first to prune the search space significantly. 筋