题解 | #童谣寻找问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    public boolean exist (char[][] board, String word) {
        // write code here
        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, i, j, 0, visited)) {
                    return true;
                }
            }
        }

        return false;
    }

    private boolean backtrack(char[][] board, String word, int row, int col,
                              int index, boolean[][] visited) {
        if (index == word.length()) {
            return true; // All characters in the word are found
        }

        if (row < 0 || row >= board.length || col < 0 || col >= board[0].length ||
                visited[row][col] || board[row][col] != word.charAt(index)) {
            return false;
        }

        visited[row][col] = true; // Mark the current cell as visited

        // Explore adjacent cells in all four directions
        boolean found = backtrack(board, word, row - 1, col, index + 1, visited) ||
                        backtrack(board, word, row + 1, col, index + 1, visited) ||
                        backtrack(board, word, row, col - 1, index + 1, visited) ||
                        backtrack(board, word, row, col + 1, index + 1, visited);

        visited[row][col] = false; // Backtrack and mark the cell as not visited

        return found;
    }
}

知识点分析：

1. 回溯算法：通过递归尝试所有可能的路径来搜索目标字符串。
2. 二维数组的遍历：通过两重循环遍历二维字符网格中的每个单元格。
3. 递归：在回溯过程中使用递归来探索每个方向的可能性。
4. 布尔数组的使用：用于标记已经访问过的单元格，避免重复使用。

解题思路：

在代码中，我们首先遍历二维字符网格，寻找起始字符与目标字符串的首字符匹配的位置。一旦找到匹配的位置，就通过回溯算法开始搜索。在每一步中，我们检查当前单元格是否与目标字符串中的字符匹配，然后递归地探索四个方向的相邻单元格。如果在某个方向上找到了完整的目标字符串，返回true；否则，撤销标记并返回false。