LeetCode（cai鸟之路）79 单词搜索

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例

输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED” 输出：true 输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE” 输出：true 输入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB” 输出：false

代码：

class Solution {
          
   
    public static boolean exist(char[][] board, String word) {
          
   

        //设置一个访问数组，为1时说明已经遍历过
        int[][] visited = new int[board.length][board[0].length];
        for (int i = 0;i<board.length;i++){
          
   
            for (int j = 0;j<board[i].length;j++){
          
   
                //如果匹配到第一个字母进入递归
//                System.out.println(i+" "+j+" "+board[i][j]);
                if (board[i][j] == word.charAt(0)){
          
   
                    visited[i][j] = 0;
                    if (dfs(board,visited,0,i,j,word)){
          
   
                        return true;
                    }else {
          
   
                        continue;
                    }
                }
            }
        }


        return false;
    }

    public static boolean dfs(char[][] board,int[][] visited,int index,int i,int j,String word){
          
   
        //首先声明边界条件,超出边界了直接返回false
        if (i<0||i>=board.length||j<0||j>=board[0].length || board[i][j] != word.charAt(index)){
          
   
            return false;
        }
        if (index == word.length()-1){
          
   
            return true;
        }else {
          
   
            char temp = board[i][j];
            board[i][j] = *;
            boolean isFind = dfs(board,visited,index+1,i-1,j,word)||dfs(board,visited,index+1,i,j+1,word)
                    ||dfs(board,visited,index+1,i+1,j,word)||dfs(board,visited,index+1,i,j-1,word);
            board[i][j] = temp;
            return isFind;
        }

    }
}

分析

通过读题，很容易知道这题时通过递归遍历去求解问题，那从哪开始递归呢，我们其实不需要从二维数组的第一个元素诶个进行dfs，我们只需要先遍历二维数组，找到和给定的word中第一个字母相同的元素，从这个位置开始进行深度遍历与递归，深度遍历需要对找到的这个元素的四个方位进行递归求解，如果当前递归函数指向与word中的元素相同，就返回true，当前递归肯定要有结束的条件。 本题中的条件有两个，一个就是是否数组越界，是否相等；还有就是是否已经全部找到了，如果分别满足条件就返回，结束当前的递归过程。