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.

Tips:

以board上的每个cell为出发点，利用depth first search向上下左右四个方向搜索匹配word。搜索的时候要考虑board的边界，cell是否已经在DFS的路径上被用过，以及cell上的值是否与word的当前字符匹配。为了跟踪DFS的路径避免同一个cell被访问多次，使用一个visited矩阵来代表board上任意的cell(i, j)是否已经被访问过。

一定注意visited的重置。

Code：

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

    public boolean recursive(char[][] board, String word, int index, int row,  
            int col, int rowLimit, int colLimit, boolean[][] visited) {  
        if (index == word.length())  
            return true;  
        // out of bounds  
        if (row < 0 || col < 0 || row >= rowLimit || col >= colLimit)  
            return false;  
        // at a visited node  
        if (visited[row][col])  
            return false;  
        // the two chars do not match  
        if (board[row][col] != word.charAt(index))  
            return false;  
        // dfs  
        visited[row][col] = true;  
        boolean result = recursive(board, word, index + 1, row + 1, col,  
                rowLimit, colLimit, visited)  
                || recursive(board, word, index + 1, row - 1, col, rowLimit,  
                        colLimit, visited)  
                || recursive(board, word, index + 1, row, col + 1, rowLimit,  
                        colLimit, visited)  
                || recursive(board, word, index + 1, row, col - 1, rowLimit,  
                        colLimit, visited);  
        visited[row][col] = false;  
        return result;  
    }  
}