[Leetcode][第79题][JAVA][单词搜索][DFS][回溯]

冷不防 2022-12-06 12:44 131阅读 0赞

#### 【问题描述】\[中等\] ####

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

#### 【解答思路】 ####

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

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

###### 1. DFS繁琐版本 ######

class Solution { 
          public boolean exist(char[][] board, String word) { 
            boolean flag = false;
    
            int row= board.length;
            int col= board[0].length;
    
            boolean[][]  used = new boolean[row][col];
            for (int i = 0; i <row ; i++) { 
                for (int j = 0; j <col ; j++) { 
                        flag = dfs(board,word,used,i,j,0);
                        if(flag){ 
                            return  true;
                        }
                    }
                }
            return  false;
        }
    
        private boolean dfs(char[][] board, String word,boolean[][] used,int x,int y ,int start) { 
            int[] dx ={ 0,1,0,-1};
            int[] dy ={ 1,0,-1,0};
            boolean flag = false;
    
            int row= board.length;
            int col= board[0].length;
            if (start == word.length() - 1) { 
                return board[x][y] == word.charAt(start);
            }
            if(board[x][y] == word.charAt(start)){ 
                used[x][y] =true;
                for (int i = 0; i <4 ; i++) { 
                    int newx = x+dx[i];
                    int newy = y+dy[i];
                    if(inArea(newx,newy,row,col) && !used[newx][newy]){ 
                        flag = dfs(board,word,used,newx,newy,start+1);
                        if(flag){ 
                            return  true;
                        }
                    }
    
                }
                used[x][y] =false;
            }
    
        return false;
    
        }
    
    
        private boolean inArea(int x,int y,int row,int col){ 
            return  x>=0 && y>=0 && x<row && y<col;
        }
    }

###### 2. DFS优化版本 ######

public 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 (inArea(newX, newY) && !marked[newX][newY]) { 
                        if (dfs(newX, newY, start + 1)) { 
                            return true;
                        }
                    }
                }
                marked[i][j] = false;
            }
            return false;
        }
    
        private boolean inArea(int x, int y) { 
            return x >= 0 && x < m && y >= 0 && y < n;
        }
    
        public static void main(String[] args) { 
    
    // char[][] board =
    // { 
    // {'A', 'B', 'C', 'E'},
    // {'S', 'F', 'C', 'S'},
    // {'A', 'D', 'E', 'E'}
    // };
    //
    // String word = "ABCCED";
    
    
            char[][] board = { { 'a', 'b'}};
            String word = "ba";
            Solution solution = new Solution();
            boolean exist = solution.exist(board, word);
            System.out.println(exist);
        }
    }
    
    作者：liweiwei1419
    链接：https://leetcode-cn.com/problems/word-search/solution/zai-er-wei-ping-mian-shang-shi-yong-hui-su-fa-pyth/

#### 【总结】 ####

###### 1. 一开始没审题 以后是不回头的遍历 审题!!! ######

###### 2.往往空间优先于时间 ######

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

###### 3.回溯算法相关题目 ######

[\[Leedcode\]\[JAVA\]\[第46题\]\[全排列\]\[回溯算法\]][Leedcode_JAVA_46]  
[\[Leetcode\]\[第81题\]\[JAVA\]\[N皇后问题\]\[回溯算法\]][Leetcode_81_JAVA_N]  
[\[Leetcode\]\[第60题\]\[JAVA\]\[第k个排列\]\[回溯\]\[DFS\]\[剪枝\]][Leetcode_60_JAVA_k_DFS]  
[\[Leetcode\]\[第39题\]\[JAVA\]\[组合总和\]\[回溯\]\[dfs\]\[剪枝\]][Leetcode_39_JAVA_dfs]

转载链接：https://leetcode-cn.com/problems/word-search/solution/zai-er-wei-ping-mian-shang-shi-yong-hui-su-fa-pyth/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/d3d767391281404eaf5410085852352e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/0e7b150004164171b584dc764bed247e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/33aae56b0d6441cc95f60d0377c5991e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/2cde13fd80f44286b10e3965b1c381af.png
[Leedcode_JAVA_46]: https://blog.csdn.net/dadongwudi/article/details/105760561
[Leetcode_81_JAVA_N]: https://blog.csdn.net/dadongwudi/article/details/108379661
[Leetcode_60_JAVA_k_DFS]: https://blog.csdn.net/dadongwudi/article/details/108419966
[Leetcode_39_JAVA_dfs]: https://blog.csdn.net/dadongwudi/article/details/108485315