题解 | 单词搜索

import java.util.*;

//思路其实很简单，就是遍历整个二维数组，利用深度优先遍历，即可完成本提
public class Solution {
    int m, n;//m行高，n列宽
    //用于深度优先遍历
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    //标记是否遍历过
    boolean[][] vis;
    //目标单词
    char[] word;

 public boolean exist (String[] board, String _word){
   //初始化
    m = board.length;
    n = board[0].length();
    vis = new boolean[m][n];
    word = _word.toCharArray();
    for(int i = 0; i < m; i++){//二维数组中每个位置都进行深度优先遍历
        for(int j = 0; j < n; j++){
            if(board[i].charAt(j) == word[0]){//有一个返回true了我们就返回true
                if(dfs(board, i, j, 0) == true) return true;
                }
            }
    }//遍历完了都没结果说明没有符合条件的
   return false;
}

 public boolean dfs(String[] board, int i, int j, int pos){
   //当前遍历到了单词最后一个字母，说明匹配成功了
    if(pos == word.length - 1){
        return true;
        }
        vis[i][j] = true;//遍历到了就标记已经走过这里了
        for(int k = 0; k < 4; k++){
            int x = i + dx[k], y = j + dy[k];
            if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && 
            board[x].charAt(y) == word[pos + 1]){//满足条件就继续深度优先遍历
                if(dfs(board, x, y, pos + 1)) return true;
            }
        }//如果四周都没找到，就说明不在这条路上，同样把标记去除，返回false
        vis[i][j] = false;
        return false;
        }
}