Word Search

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

For example,
Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

在一个二维的数组中找到一个目标单词。我们可以用深度优先搜索来解决，用递归来完成。用一个辅助的布尔型数组来记录当前元素是否已经被访问过。DFS的时候要注意检查边界情况，检查下标是否越界。用一个变量lth来记录当然查找到的可以匹配的长度，如果lth等于带匹配字符串的长度就返回true。代码如下：

public class Solution {
    public boolean exist(char[][] board, String word) {
        if(word == null || word.length() == 0) 
            return true;
        else if(board == null || board.length == 0) 
            return false;
        boolean[][] isVisited = new boolean[board.length][board[0].length];
        for(int i = 0; i < board.length; i++)
            for(int j = 0; j < board[0].length; j++) {
                if(board[i][j] == word.charAt(0)) {
                    isVisited[i][j] = true;
                    boolean top = DFS(i - 1, j, 1, word, board, isVisited);
                    boolean bottom = DFS(i + 1, j, 1, word, board, isVisited);
                    boolean left = DFS(i, j - 1, 1, word, board, isVisited);
                    boolean right = DFS(i, j + 1, 1, word, board, isVisited);
                    
                    if(top || bottom || left || right)
                        return true;
                    else
                    isVisited[i][j] = false;
                }
            }
            return false;
    }
    public boolean DFS(int i, int j, int lth, String word, char[][] board, boolean[][] isVisited) {
        if(word.length() == lth) return true;
        if(i < 0 || i == board.length || j < 0 || j == board[0].length) return false;
        if(!isVisited[i][j] && board[i][j] == word.charAt(lth)) {
                    isVisited[i][j] = true;
                    boolean top = DFS(i - 1, j, lth + 1, word, board, isVisited);
                    boolean bottom = DFS(i + 1, j, lth + 1, word, board, isVisited);
                    boolean left = DFS(i, j - 1, lth + 1, word, board, isVisited);
                    boolean right = DFS(i, j + 1, lth + 1, word, board, isVisited);
                    
                    if(top || bottom || left || right)
                        return true;
                    else
                    isVisited[i][j] = false;
                }
        return false;
    }
}