leetcode79. 单词搜索网格地图搜索+回溯经典写法啦

小灰灰 2023-07-07 05:59 2阅读 0赞

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

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

示例:

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

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

思路：搜索回溯基本上是经典模板题了。

class Solution {
        private boolean[][] marked;
        //        x-1,y
        // x,y-1  x,y    x,y+1
        //        x+1,y
        private int[][] direction = {
       {-1, 0}, {0, -1}, {0, 1}, {1, 0}};
        // 盘面上有多少行
        private int m;
        // 盘面上有多少列
        private int n;
        private String word;
        private char[][] board;
        public boolean exist(char[][] board, String word) {
            m = board.length;
            if (m == 0)return false;
            n = board[0].length;
            marked = new boolean[m][n];
            this.word = word;
            this.board = board;
    
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (dfs(i, j, 0))
                        return true;
            return false;
        }
    
        private boolean dfs(int i, int j, int start) {
            if (start == word.length() - 1) {
                return board[i][j] == word.charAt(start);
            }
            if (board[i][j] == word.charAt(start)) {
                marked[i][j] = true;
                for (int k = 0; k < 4; k++) {
                    int newX = i + direction[k][0];
                    int newY = j + direction[k][1];
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && !marked[newX][newY]) {
                        if (dfs(newX, newY, start + 1)) {
                            return true;
                        }
                    }
                }
                marked[i][j] = false;
            }
            return false;
        }
    }