题解 | #童谣寻找问题#

题目考察的知识点是：

本题主要考察知识点是搜索。

题目解答方法的文字分析：

本题往深度遍历有四个方向进行选择，所以我们需要往四条路上进行遍历，如果遍历到之前已经遍历过的地方或者遍历位置已经超过数组下标我们则结束继续遍历。如果需要一个标志数组用来记录我们已经遍历过的位置，很多人这题可能会忽略使用标志数组来记录已经遍历过的位置。

本题解析所用的编程语言：

java语言。

完整且正确的编程代码：

import java.util.*;


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

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

}