题解 | #童谣寻找问题#

知识点：二维数组，回溯，广度优先搜索

对于在二维数组中的搜索问题，首先要想到的就是对每一个点进行四个方向上的遍历，而这道题特殊的点在于我们要按规定的顺序进行查找，故需要字符串来约束我们进行查找的范围，使用一个visited二维数组来对使用过的字符进行标记，防止重复使用，当我们的搜索长度达到字符串的长度时，即为找到了目标字符串，即可停止后续的搜索。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param board char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    private String word;
    private int m, n;
    private char[][] board;
    private boolean[][] visited;
    private int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    private boolean flag = false;

    public boolean exist (char[][] board, String word) {
        // write code here
        this.word = word;
        this.board = board;
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                backTracking(i, j, 0);
            }
        }
        return flag;
    }

    private void backTracking(int x, int y, int index) {
        if(index == word.length()) {
            flag = true;
            return;
        }
        if(flag || x < 0 || x >= m || y < 0 || y >= n || visited[x][y] || board[x][y] != word.charAt(index)) {
            return;
        }
        visited[x][y] = true;
        for(int[] dir: dirs) {
            backTracking(x + dir[0], y + dir[1], index + 1);
        }
        visited[x][y] = false;
    }
}