题解 | #童谣寻找问题#

题目考察的知识点

考察回溯算法

题目解答方法的文字分析

回溯算法在深度优先搜索上的应用，为了记录每个位置是否被访问，从而在访问过的位置用特殊符号“#”代替，在回溯的时候还原。具体的细节参看代码与注释。

本题解析所用的编程语言

使用Java解答

完整且正确的编程代码

import java.util.*;


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

    public boolean dfs(String word, int i, int j, char[][] board, int index){
        if(index == word.length()) return true; //已经遍历完的时候返回true
        if(i<0||i>=board.length||j<0||j>=board[0].length||board[i][j]!=word.charAt(index)||board[i][j]=='#') return false; //越界或者此时位置上的字符和要访问的字符不一致的时候都返回false
        char temp = board[i][j]; //记录
        board[i][j] = '#'; //做标记 表示已经访问过该位置
        index+=1;
        if(dfs(word,i-1,j,board,index)||dfs(word,i+1,j,board,index)||dfs(word,i,j-1,board,index)||dfs(word,i,j+1,board,index)){  //继续在四个方向下寻找
            return true;
        }else{
            board[i][j] = temp; //回溯的时候还原该位置上的字符
            return false;
        }
    }
}