http://www.lintcode.com/en/problem/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.

Example Given board = [ "ABCE", "SFCS", "ADEE" ] word = "ABCCED", -> returns true, word = "SEE", -> returns true, word = "ABCB", -> returns false.

解题 ：在matrix里面找start point， 找到了之后做dfs看是否有符合word的path。

public class Solution {
    /**
     * @param board: A list of lists of character
     * @param word: A string
     * @return: A boolean
     */
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0)
            return false;
        if(word.length() == 0)
            return true;
        //遍历matrix，O(n^2)
        for(int i = 0; i< board.length; i++){
            for(int j = 0; j< board[0].length; j++){
                if(board[i][j] == word.charAt(0)){

                    boolean rst = find(board, i, j, word, 0);
                    if(rst)
                        return true;
                }
            }
        }
        return false;
    }

    private boolean find(char[][] board, int i, int j, String word, int start){
        //'start' 用来看word匹配长度，当等于word长度我们就找到了匹配
        if(start == word.length())
            return true;
        //prune，检查边界条件，出界或者不匹配就返回上一层。
        if (i < 0 || i>= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(start)){
            return false;
        }

        board[i][j] = '#'; // should remember to mark it
        boolean rst = find(board, i-1, j, word, start+1) 
        || find(board, i, j-1, word, start+1) 
        || find(board, i+1, j, word, start+1) 
        || find(board, i, j+1, word, start+1);
        board[i][j] = word.charAt(start);
        return rst;
    }
}