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.

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Solution

1. Scan every entry in the matrix, to check if it’s possible to starts a path；（matrix中每个字母都需要被尝试一遍）
2. When an entry matches a character in the path, move on to the adjacent entries to match the next character
3. 题目要求，The same letter cell may not be used more than once； 则需要记录已经被访问过的数字，已经访问了的就不能再访问了。

Recursive Base Case: 满足条件且已经访问的字母数 == given word 长度，说明已经在matrix中找到该word，返回true

class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board [0].length == 0 || word == null || word.length () == 0) {
            return false;
        }
        
        boolean[][] visited = new boolean [board.length][board[0].length];
        int[] visitedPathLength = { 0 };
        
        // Scan every entry in the matrix, to check if it’s possible to starts a path
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board [0].length; j++) {
                if (findWord (board, visited, word, visitedPathLength, i, j)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean findWord (char[][] board, boolean[][] visited, String word, int[] visitedPathLength, int row, int col) {
        if (visitedPathLength[0] == word.length ()) {
            return true;
        }
        
        // try 4 directions of current character, trying to find the next character
        int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        
        // must satisfy 
        // 1) current character is the right one in the word 
        // 2) this character hasn't been visited
        boolean canContinue = row >= 0 && row < board.length && col >= 0 && col < board[0].length
                              && board[row][col] == word.charAt (visitedPathLength[0])
                              && !visited[row][col];
        if (canContinue) {
            // if can continue, need to mark current character as Visited, and increment the visitedPathLength
            visited[row][col] = true;
            visitedPathLength[0] ++;
            
            // try all 4 directions, if find the word in any direction, return true;
            for (int[] dir : directions) {
                if (findWord (board, visited, word, visitedPathLength, row + dir[0], col + dir[1])) {
                    return true;
                }
            }
            
            visited[row][col] = false;
            visitedPathLength[0] --;
        }
        
        return false;
    }
}