leetcode:79. 单词搜索

Dear 丶 2023-06-24 12:21 136阅读 0赞

## 题目: ##

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

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

示例:

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

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

## 分析: ##

深搜+回溯,使用二维boolean数组记录访问状态

## 代码: ##

class Solution {
        int x;
        int y;
        boolean[][] visited;
    
        public boolean exist(char[][] board, String word) {
            x = board.length;
            y = board[0].length;
            visited = new boolean[x][y];
            for (int i = 0; i < x; i++) {
                for (int j = 0; j < y; j++) {
                    if (dfs(board, i, j, word, 0)) {
                        return true;
                    }
                }
            }
            return false;
        }
    
        private boolean dfs(char[][] board, int i, int j, String word, int index) {
            if (word.length() == index) {
                return true;
            }
            if (crossBoundary(i, j)) {
                return false;
            }
            if (visited[i][j]) {
                return false;
            }
            if (word.charAt(index) != board[i][j]) {
                return false;
            }
            visited[i][j] = true;
            if (dfs(board, i + 1, j, word, index + 1)) {
                return true;
            }
            if (dfs(board, i - 1, j, word, index + 1)) {
                return true;
            }
            if (dfs(board, i, j + 1, word, index + 1)) {
                return true;
            }
            if (dfs(board, i, j - 1, word, index + 1)) {
                return true;
            }
            visited[i][j] = false;
            return false;
        }
    
        private boolean crossBoundary(int i, int j) {
            if (i < 0 || i >= x) {
                return true;
            }
            if (j < 0 || j >= y) {
                return true;
            }
            return false;
        }
    
    }

## 效率: ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]

## 总结: ##

典型题目,学会套路就行

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191223104534783.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0NTE2NTQ5,size_16,color_FFFFFF,t_70