单词搜索与解数独

单词搜索（LeetCode 79）

在二维网格中，从任意格子出发，上下左右相邻，是否能拼出目标单词。

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

private boolean dfs(char[][] board, String word, int k,
                    int i, int j, boolean[][] visited) {
    if (k == word.length()) return true;
    int m = board.length, n = board[0].length;
    if (i < 0 || i >= m || j < 0 || j >= n) return false;
    if (visited[i][j] || board[i][j] != word.charAt(k)) return false;
    visited[i][j] = true;
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    for (int[] d : dirs)
        if (dfs(board, word, k + 1, i + d[0], j + d[1], visited)) {
            visited[i][j] = false;
            return true;
        }
    visited[i][j] = false;
    return false;
}

单词搜索 II（LeetCode 212）

给定单词列表，在网格中找出所有能拼出的单词。

优化：先把单词列表建成 Trie，DFS 同时在矩阵和 Trie 上走，避免重复搜索。

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word;    // 叶节点存完整单词
}

public List<String> findWords(char[][] board, String[] words) {
    TrieNode root = new TrieNode();
    for (String w : words) {
        TrieNode cur = root;
        for (char c : w.toCharArray()) {
            if (cur.children[c-'a'] == null) cur.children[c-'a'] = new TrieNode();
            cur = cur.children[c-'a'];
        }
        cur.word = w;
    }
    List<String> res = new ArrayList<>();
    int m = board.length, n = board[0].length;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            dfs(board, i, j, root, res);
    return res;
}

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

解数独（LeetCode 37）

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] = '.';
                }
            }
            return false;   // 没有合法数字，回溯
        }
    }
    return true;
}

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;
        if (board[i][col] == c) return false;
        int r = 3 * (row / 3) + i / 3;
        int cl = 3 * (col / 3) + i % 3;
        if (board[r][cl] == c) return false;
    }
    return true;
}

剪枝优化：提前计算每个空格可用数字的位掩码，优先填候选数最少的格子（"最约束优先"策略）。