给定一个 2D 棋盘和一个单词，找出该单词是否存在于网格中。

单词可以由顺序相邻单元格的字母构成，其中“相邻”单元格是水平或垂直相邻的单元格。 同一个字母单元格不能多次使用。

例如，给定板 =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = “ABCCED”，-> 返回true，
word = “SEE”，-> 返回true，
word = “ABCB”，-> 返回 false。

Java 解决方案

这个问题可以通过使用典型的 DFS 算法来解决。

public boolean exist(char[][] board, String word) {
    int m = board.length;
    int n = board[0].length;
 
    boolean result = false;
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
           if(dfs(board,word,i,j,0)){
               result = true;
           }
        }
    }
 
    return result;
}
 
public boolean dfs(char[][] board, String word, int i, int j, int k){
    int m = board.length;
    int n = board[0].length;
 
    if(i<0 || j<0 || i>=m || j>=n){
        return false;
    }
 
    if(board[i][j] == word.charAt(k)){
        char temp = board[i][j];
        board[i][j]='#';
        if(k==word.length()-1){
            return true;
        }else if(dfs(board, word, i-1, j, k+1)
        ||dfs(board, word, i+1, j, k+1)
        ||dfs(board, word, i, j-1, k+1)
        ||dfs(board, word, i, j+1, k+1)){
            return true;
        }
        board[i][j]=temp;
    }
 
    return false;
}

同样，下面是编写此算法的另一种方式。

public boolean exist(char[][] board, String word) {
    for(int i=0; i<board.length; i++){
        for(int j=0; j<board[0].length; j++){
            if(dfs(board, word, i, j, 0)){
                return true;
            }
        } 
    }
 
    return false;
}
 
public boolean dfs(char[][] board, String word, int i, int j, int k){
    if(board[i][j]!=word.charAt(k)){
        return false;
    }
 
    if(k>=word.length()-1){
        return true;
    }
 
    int[] di={-1,0,1,0};
    int[] dj={0,1,0,-1};
 
    char t = board[i][j];
    board[i][j]='#';
 
    for(int m=0; m<4; m++){
        int pi=i+di[m];
        int pj=j+dj[m];
        if(pi>=0&&pi<board.length&&pj>=0&&pj<board[0].length&&board[pi][pj]==word.charAt(k+1)){
            if(dfs(board,word,pi,pj,k+1)){
                return true;
            }
        }
    }
 
    board[i][j]=t;
 
    return false;
}