面试热题（单词搜索）

ゞ浴缸里的玫瑰 2023-10-14 17:46 6阅读 0赞

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

![15de499430d363e3c9f4dfb57268a37f.jpeg][]

这种是不是和岛屿搜索的类型题是相似的，每个点都有8个位置的选择，这种类型题就可以用我们上次讲的岛屿数量的解法，通过深度优先遍历（dfs）进行解决

//设置方向  上右下左
        int[] xnum={-1,0,1,0};
        int[] ynum={0,1,0,-1};

我们可以维护一个visited数组，防止走回头路

boolean[][] visited;

递归函数中入参的变量我们看需要哪些？原数组肯定是需要的，然后我们也需要知道我们已经遍历到哪个点了，因为我们要找的是字符串，我们也要知道当前遍历到字符串的哪个索引上，函数签名如下：

private boolean dfs(char[][] board, String word, int startIndex, int x, int y) {}

如果当前遍历到字符串索引的最后一位且网格中也有相同的字符，那就说明该路径我们在网格中是可以找到的，如果找不到，直接返回false,如果当前不是字符串的最后一个索引对应的位置，在从当前元素的相邻元素不断的去进行寻找，直到找到返回true或者fasle为止

源码如下：

//设置方向  上右下左
        int[] xnum={-1,0,1,0};
        int[] ynum={0,1,0,-1};
        boolean[][] visited;
        int row;
        int column;
        public boolean exist(char[][] board, String word) {
            //对入参进行判断
            if(board==null||board.length==0||board[0].length==0){
                return false;
            }
            //从每一个点都开始进行遍历
            row=board.length;
            column=board[0].length;
            visited=new boolean[row][column];
            for (int i = 0; i <row; i++) {
                for (int j = 0; j <column; j++) {
                    //如果存在一种情况则返回true
                    if(dfs(board,word,0,i,j)){
                        return true;
                    }
                }
            }
            return false;
            }
        private boolean dfs(char[][] board, String word, int startIndex, int x, int y) {
              if(startIndex==word.length()-1){
                if(word.charAt(startIndex)==board[x][y]){
                    return true;
                }
            }
            if(word.charAt(startIndex)!=board[x][y]){
                return false;
            }else{
                //向四个方向进行寻找
                visited[x][y]=true;
                for (int i = 0; i <4; i++) {
                    int newx=x+xnum[i];
                    int newy=y+ynum[i];
                    //如果越界的话则不需要进行考虑
                    if(newx<0||newx>=row||newy<0||newy>=column||visited[newx][newy]){
                        continue;
                    }
                    if(dfs(board,word,startIndex+1,newx,newy)){
                        return true;
                    }        
                }
                //回溯
                visited[x][y]=false;
            }
            return false;
        }

[15de499430d363e3c9f4dfb57268a37f.jpeg]: https://img-blog.csdnimg.cn/img_convert/15de499430d363e3c9f4dfb57268a37f.jpeg