题解 | #童谣寻找问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    public static boolean flag = false;
    public boolean exist (char[][] board, String word) {
        // write code here
        boolean[][] visited = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                search(board, visited, i, j, word, new StringBuffer());
            }
        }
        return flag;
    }

    public void search(char[][] board, boolean[][] visited, int i, int j,
                       String word,
                       StringBuffer stringBuffer) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length ||
                visited[i][j]) {
            return;
        }
        if (stringBuffer.length() == word.length() &&
                stringBuffer.toString().equals(word)) {
            flag = true;
            return;
        }
        stringBuffer.append(board[i][j]);
        visited[i][j] = true;
        search(board, visited, i + 1, j, word, stringBuffer);
        search(board, visited, i - 1, j, word, stringBuffer);
        search(board, visited, i, j + 1, word, stringBuffer);
        search(board, visited, i, j - 1, word, stringBuffer);
        visited[i][j] = false;
        stringBuffer.deleteCharAt(stringBuffer.length() - 1);
    }
}

本题考察的知识点是递归遍历，所用编程语言是java。

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