LC 79 Word Search(M)

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.

public boolean exist(char[][] board, String word)

解题思路 Recursive, DFS

从每一点开始DFS探测，探测失败条件是，超界，或者探测值不等于 同级的字符串值。 Tips 为了不增加visited数组，通过更改 board数值为一个无效字符，探测完上下左右后再恢复。

public boolean exist(char[][] board, String word) {
    for(int row = 0; row<board.length; row++)
        for(int col = 0; col<board[0].length; col++){
            if(isMatch(board, row, col, word, 0))
                return true;
        }
        return false;
}
public boolean isMatch(char[][] board, int row, int col, String word, int index){
    if(index >= word.length())
        return true;
    if(row<0 || col<0 || row>=board.length || col>=board[0].length || board[row][col] != word.charAt(index))
        return false;
    char temp = board[row][col];
    board[row][col] = '$'; //改为无效值，表示已经访问过
    index++;
    boolean res =(isMatch(board, row-1, col, word, index) || isMatch(board, row, col-1, word, index) ||
        isMatch(board, row+1, col, word, index) || isMatch(board, row, col+1, word, index));
    board[row][col] = temp;// 探测完后，恢复
    return res;
}