Leetcode刷题java之79. 单词搜索

不念不忘少年蓝@ 2023-07-03 12:09 7阅读 0赞

执行结果：

通过

显示详情

执行用时 :7 ms, 在所有 Java 提交中击败了58.88% 的用户

内存消耗 :38.4 MB, 在所有 Java 提交中击败了56.97%的用户

题目：

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

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

示例:

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

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/word-search  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

回溯法

代码：

class Solution {
        int[][] nexts={
       {-1,0},{1,0},{0,1},{0,-1}};
        int row=0;
        int col=0;
        public boolean exist(char[][] board, String word) {
            this.row=board.length;
            this.col=board[0].length;
            boolean[][] visit=new boolean[row][col];
            for(int i=0;i<row;i++)
            {
                for(int j=0;j<col;j++)
                {
                    if(backtrack(board,word,i,j,visit,0))
                    {
                        return true;
                    }
                }
            }
            return false;
        }
        public boolean backtrack(char[][] board,String word,int i,int j,boolean[][] visit,int index)
        {
            if(index==word.length())
            {
                return true;
            }
            if(i<0||i>=row||j<0||j>=col||visit[i][j]||word.charAt(index)!=board[i][j])
            {
                return false;
            }
            visit[i][j]=true;
            for(int[] next:nexts)
            {
                if(backtrack(board,word,i+next[0],j+next[1],visit,index+1))
                {
                    return true;
                }
            }
            visit[i][j]=false;
            return false;
        }
    }