Java算法题-解析 "单词搜索" 算法问题

题目：

给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中 "相邻" 单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

引言：

"单词搜索" 是一个关于回溯算法和矩阵遍历的问题。解决这个问题需要对回溯算法和矩阵遍历有一定的理解，同时需要找到一种方法来在矩阵中搜索单词。通过解答这个问题，我们可以提升对回溯算法和矩阵遍历的考虑，同时也能拓展对矩阵搜索的思维。

算法思路：

为了在二维网格中搜索单词，我们可以使用回溯算法来进行操作。具体思路如下：

1. 遍历整个网格，找到与单词的首字母匹配的位置。
2. 对于每个匹配位置，尝试从该位置开始，沿着相邻单元格进行搜索，看是否能构成整个单词。
3. 在搜索过程中，递归调用一个辅助函数，用于检查当前位置的合法性和是否能继续搜索。
4. 如果能找到一个位置，使得从该位置开始可以构成整个单词，返回 true，表示单词存在于网格中。
5. 如果所有的搜索路径都无法构成单词，返回 false，表示单词不存在于网格中。

代码实现：

以下是使用 Java 实现的 "单词搜索" 算法的示例代码：

public class WordSearch {
    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int 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 (board[i][j] == word.charAt(0) && backtrack(board, word, visited, i, j, 0)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean backtrack(char[][] board, String word, boolean[][] visited, int row, int col, int index) {
        if (index == word.length()) {
            return true;
        }
        
        if (row < 0 || col < 0 || row >= board.length || col >= board[0].length || visited[row][col] || board[row][col] != word.charAt(index)) {
            return false;
        }
        
        visited[row][col] = true;
        if (backtrack(board, word, visited, row + 1, col, index + 1) ||
            backtrack(board, word, visited, row - 1, col, index + 1) ||
            backtrack(board, word, visited, row, col + 1, index + 1) ||
            backtrack(board, word, visited, row, col - 1, index + 1)) {
            return true;
        }
        visited[row][col] = false;
        
        return false;
    }
}

算法分析：

• 时间复杂度：在最坏情况下，需要遍历整个网格，所以时间复杂度为 O(m n 4^k)，其中 m 和 n 分别是网格的行数和列数，k 是单词的长度。
• 空间复杂度：需要一个额外的布尔数组来标记已访问的单元格，所以空间复杂度为 O(m * n)。

示例和测试：

假设给定二维网格 board 和单词 word = "ABCCED"，根据算法，单词存在于网格中。

我们可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        WordSearch solution = new WordSearch();
        char[][] board = {
            {'A','B','C','E'},
            {'S','F','C','S'},
            {'A','D','E','E'}
        };
        String word = "ABCCED";
        boolean exists = solution.exist(board, word);

        System.out.println("Word exists in board: " + exists);
    }
}

总结：

"单词搜索" 算法题要求在二维网格中搜索单词，是一个关于回溯算法和矩阵遍历的问题。通过实现这个算法，我们可以提升对回溯算法和矩阵遍历的考虑，同时也能拓展对矩阵搜索的思维。这个问题强调了如何使用回溯算法在矩阵中搜索目标单词。