Problem

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

Given board =

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

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.

Note

建立helper函数，当board[i][j]和word的第一个字符相等，将board[i][j]置为非字母的其它字符，防止这个元素再一次被调用，然后递归调用helper函数判断board[i][j]的上下左右相邻的字符是否和word的下一个字符相等并将结果存入res，再把board[i][j]置回原来的字符（可能和word.charAt(0)相同的字符在board[][]中有多种情况，而此解并非正解，故还原数组在main函数里继续循环），然后递归返回res到上一层helper函数。
当递归到第word.length次时，helper被调用了word.length+1次。说明整个word已经被找到，返回true。
回到main函数，遍历整个board数组，当helper函数返回true时，才返回true；否则在循环结束之后返回false。

Solution

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) return false;
        int m = board.length, n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0) && helper(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
    public boolean helper(char[][] board, String word, int i, int j, int start) {
        if (start == word.length()) return true;
        if (i >= 0 && i < board.length && j >= 0 && j < board[0].length && board[i][j] == word.charAt(start)) {
            board[i][j] = '$';
            boolean res = helper(board, word, i+1, j, start+1) || helper(board, word, i-1, j, start+1) || helper(board, word, i, j+1, start+1) || helper(board, word, i, j-1, start+1);
            board[i][j] = word.charAt(start);
            return res;
        }
        return false;
    }
}