Java 题解 | #童谣寻找问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    boolean flag = false;

    public boolean exist(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0)) {
                    int[][] vis = new int[m][n];
                    dfs(board, vis, word, 0, i, j);

                    if (flag) {
                        return flag;
                    }
                }
            }
        }

        return false;
    }

    private void dfs(char[][] board, int[][] vis, String word, int index, int i,
                     int j) {
        if (flag) {
            return;
        }

        if (index == word.length()) {
            flag = true;
            return;
        }

        int m = board.length;
        int n = board[0].length;

        if (i < 0 || i >= m || j < 0 || j >= n || vis[i][j] == 1 ||
                board[i][j] != word.charAt(index)) {
            return;
        }

        vis[i][j] = 1;
        dfs(board, vis, word, index + 1, i + 1, j);
        dfs(board, vis, word, index + 1, i - 1, j);
        dfs(board, vis, word, index + 1, i, j + 1);
        dfs(board, vis, word, index + 1, i, j - 1);

        vis[i][j] = 0;
    }
}

编程语言是Java。

该题考察的知识点包括：

• 二维数组的遍历
• 递归（深度优先搜索）
• 条件判断和逻辑控制

代码的文字解释如下：

1. 编写一个 exist 方法，接受一个字符类型的二维数组 board 和一个字符串类型的单词 word 作为参数，并返回一个布尔值。
2. 在 exist 方法中，获取二维数组 board 的行数和列数，分别赋值给变量 m 和 n。
3. 使用两层循环遍历二维数组 board，通过比较当前元素与目标单词的首字母是否相等来确定起始位置。
4. 如果找到起始位置，就创建一个与二维数组 board 同样大小的二维数组 vis，用于标记访问过的元素。
5. 调用递归函数 dfs，传入二维数组 board、 vis、目标单词 word、当前字符下标 0、起始位置的行索引 i 和列索引 j。
6. 如果在递归过程中找到了目标单词，则将 flag 设置为 true，并立即返回。
7. 在递归函数 dfs 中，首先判断是否已经找到了目标单词（flag 为 true），如果是，则直接返回。
8. 判断递归终止条件，即当前字符下标是否等于目标单词的长度。若相等，则说明已经找到了目标单词，将 flag 设置为 true，并立即返回。
9. 判断越界情况，如果当前位置超出了二维数组范围、或者当前位置已经被访问过、或者当前位置的字符与目标单词中对应位置的字符不相等，则返回。
10. 将当前位置标记为已访问，即将 vis[i][j] 设置为 1。
11. 调用递归函数 dfs，分别向四个方向上进行搜索，即向右移动一列、向左移动一列、向下移动一行、向上移动一行，并将当前字符下标加 1。
12. 当递归函数返回后，将当前位置的访问状态重置为未访问，即将 vis[i][j] 设置为 0。
13. 返回 flag 的值，即是否找到了目标单词。