剑指offer—矩阵中的路径(单词搜索) 解答

剑指offer—矩阵中的路径(单词搜索)

题目描述

给定一个二维网格和一个单词,找出该单词是否存在于网格中。


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

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

思路

这题是一个暴力搜索的题目,只需要使用回溯+递归找到符合条件的路径就好了,从二维数组中每一个起点开始判断,如果该起点开始的找到了符合的字符串,就返回true,否则返回false

  • 递归如下函数,chars为二位数组,word为需要查找的单词,u为该单词中递归到的第几个字符,x为遍历到二维数组中的横坐标,y为遍历到二维数组中的纵坐标

dfs(char[][] chars,String word,int u,int x,int y)

  • 递归流程:

    1. 判断u和word的长度是否相等,相等则说明已经匹配了该字符串,返回true
    2. 如果word.charAt(u)chars[x][y]不相等,说明不匹配,不用判断该路径其他位置了,直接返回false
    3. 设置该点所在字符为一个不会被判断正确的字符,防止重复访问
    4. 递归上下左右四种情况,有符合的返回true,都没有则先把刚刚设置的字符设置为原来的字符,再返回false
  • 难点1:如何保证不往回遍历

    题目要求我们不能往回查找,我们可以在每次递归搜索时把访问过的点在二维数组中的位置的值设置为一个不同的值(比如@),但是要在每一次递归完成后把该值设置回去(回溯),不然下次其他路径来到这个点的查找就会失败

代码

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board.length==1&&board[0].length==1&&word.length()==1) return board[0][0]==word.charAt(0);
        for(int i=0;i<board.length;i++)
            for(int j=0;j<board[i].length;j++)
                if(dfs(board,word,0,i,j))
                    return true;
        return false;
    }
    public boolean dfs(char[][] chars,String word,int u,int x,int y){
        if(u==word.length()) return true;
        if(chars[x][y]!=word.charAt(u)) return false;
        chars[x][y] = '@';
        int []dx = new int[]{0,0,-1,1};int []dy = new int[]{1,-1,0,0};
        for(int i=0;i<4;i++){
            int xi = x + dx[i]; int yi = y + dy[i];
            if(xi>=0&&yi>=0&&xi<chars.length&&yi<chars[xi].length){
                //return dfs(chars,word,u+1,xi,yi);
                //注意这里不能直接返回,还需要判断其他路径,应该当找到路径的时候才返回true
                if(dfs(chars,word,u+1,xi,yi)) return true;
            }
        }
        chars[x][y] = word.charAt(u);
        return false;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/matrix-path.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!