79.单词搜索

发表于： 分类于：
字数： 1341 阅读：≈ 3分钟

🏳️‍🌈 79.单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

思路

基本思想

为了从board中找到给定的单词,需要在board中搜索,只要找到一条完整的路径,且路径中的元素只被使用一次,那么就相当于找到了单词,对于这条路径来说,不一定非要一直向着一个方向,所以当处于一个节点时,可以向上下左右四个方向移动,所以这种搜索有点像图论中的岛屿问题,所以可以依次从board中的每一个位置出发,尝试搜索出一条合法的路径

对于board中的每一个位置来说,当当前位置无法与word中的元素匹配,那么就没有从这个位置出发的必要,直接返回false,当当前元素与word中的元素匹配,才可以进行下面的匹配

由于每一步的移动的前提是当前位置与word中的元素匹配,当当前元素匹配到了word中的最后一个位置的元素时,说明已经找到了一条路径,这条路径形成了word,此时可以逐层向上返回true,整个程序这里是递归返回点

当没有到达递归返回点,且当前位置匹配word中的元素时,需要从当前位置出发,向上下左右开始搜索,尝试找到下一个匹配的位置,找到了继续向下,没找到就返回false

总结整体的流程就是依次从board中的每一个元素出发,尝试找到形成word的一条路径,形成一个图的搜索形式,出现一个匹配的位置,就从这个位置继续向下匹配

执行流程

  1. 依次从board中的每一个元素出发进行搜索,形成一个图的搜索形式
  2. 当前元素与word的位置不匹配,直接返回false
  3. 当前元素与word的位置匹配,且匹配到了最后一个元素,直接返回true,递归从这里开始向上逐层返回true
  4. 当前元素与word的位置匹配,但是没到最后一个元素,此时需从当前元素出发,向上下左右遍历那些没访问过的元素,四个方向只要有一个方向匹配成功,就会继续向下匹配,如果没有一个位置匹配成功,此时就会逐层返回false,最终整个方法返回false,程序会继续选择board的下一个元素进行搜索,重复1的步骤

代码

根据以上分析,得出以下代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
    public boolean exist(char[][] board, String word) {
        boolean[][] isVisited=new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;++i){
            for(int j=0;j<board[0].length;++j){
                if(backtrack(board,isVisited,word,0,i,j))
                    return true;
            }
        }
        return false;
    }
    public boolean backtrack(char[][] board, boolean[][] isVisited,
                             String word,int index,int x,int y){
        if(board[x][y]!=word.charAt(index))
            return false;
            //这里是最后一个位置也匹配,此时直接返回true
        else if(index==word.length()-1)//只有这里返回true
            return true;
        //到这里时当前位置匹配,但是没有到最后一个位置,需要继续向下匹配
        isVisited[x][y]=true;
        //从当前位置往上下左右开始遍历,尝试找到匹配的字符
        //代表当前位置移动的距离,也就是变成上下左右
        int[][] directions={{-1,0},{1,0},{0,-1},{0,1}};
        //从当前位置出发,向上下左右开始走
        for(int[] dir:directions){
            int newx=x+dir[0],newy=y+dir[1];
            if(newx>=0&&newx<board.length&&newy>=0&&newy<board[0].length){
                if(!isVisited[newx][newy]){
                    boolean flag=
                        backtrack(board,isVisited,word,index+1,newx,newy);
                    if(flag){
                        return true;
                    }
                }
            }
        }
        isVisited[x][y]=false;
        //说明当前位置查找失败
        return false;
    }

}

总结

可以将搜索过程看做是一个图论中的岛屿问题,从一个点出发,向上下左右搜索,尝试找到形成word的路径,当前点找不到,继续从board中的下一个点开始找,直到board中所有的点都搜索过都没找到,此时返回false,但是只要有一个点能找到就一定会返回true