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

import java.util.*;


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

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

编程语言是Java。

这道题考察了回溯算法和深度优先搜索（DFS）的应用。

该代码的文字解释大纲如下：

1. 在 exist 方法中，判断输入的二维字符数组是否为空，若为空则返回 false。获取二维字符数组的行数 m 和列数 n。创建一个与二维数组大小相同的布尔型二维数组 visited，用于记录每个位置是否被访问过。
2. 遍历二维字符数组的所有位置：调用 backtrack 方法进行回溯，传入当前的行、列、索引（表示已匹配的字符数）以及布尔型二维数组 visited。如果 backtrack 方法返回 true，表示找到了符合条件的单词，直接返回 true。
3. 若遍历完二维字符数组后仍未找到符合条件的单词，返回 false。
4. 在 backtrack 方法中，首先判断当前索引是否等于单词的长度，若是，则找到了完整的单词，返回 true。
5. 接着判断当前位置是否越界、已经被访问过或者当前字符不匹配，若满足任一条件，则返回 false。
6. 将当前位置标记为已访问，然后递归调用 backtrack 方法分别对当前位置的上、下、左、右四个方向进行搜索。
7. 如果其中任一方向上找到了符合条件的单词，返回 true。
8. 将当前位置标记为未访问，表示回溯到上一层。
9. 若在所有方向上都未能找到符合条件的单词，则返回 false。