【LeetCode刷题】-- 79.单词搜索

79.单词搜索

方法：使用回溯

使用dfs函数表示判断以网格的(i.j)位置出发，能否搜索到word(k)，其中word(k)表示字符串word从第k个字符开始的后缀子串，如果能搜索到，返回true,反之返回false

• 如果board[i][j]≠word[k]，当前字符串不匹配，直接返回false
• 如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回true
• 否则，遍历当前位置的所有相邻位置，如果从某个相邻位置出发，能搜索到子串word[k+1,…]，则返回true,否则返回false

为了防止重复遍历相同的位置，需要额外维护一个visited数组，用于标识每个位置是否被访问过，每次遍历相邻位置时，需要跳过已经被访问的位置

class Solution {
    
    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                boolean flag = dfs(board,word,i,j,visited,0);
                if(flag){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word,int r,int c,boolean[][] visited,int index){
      if(board[r][c]!=word.charAt(index)){
          return false;
      }else if(index == word.length() - 1){
          return true;
      }
      visited[r][c] = true;
      boolean result = false;
      int[][] direcions = {{0,1},{0,-1},{1,0},{-1,0}};  //定义方位
      for(int[] dir:direcions){
          int newrow = r + dir[0],newcol = c + dir[1];
          if(newrow>=0 && newrow < board.length && newcol>=0 && newcol<board[0].length){
              if(!visited[newrow][newcol]){
                boolean flag = dfs(board,word,newrow,newcol,visited,index+1);
                if(flag){
                  result= true;
                  break;
                }
              }
          }
      }
      visited[r][c] = false;
      return result;    
    }
}