79. 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.

Solution1：DFS (Recursive) ＋(backtracking)
Graph DFS 总结：http://www.jianshu.com/p/bdb8d5980d32
backtracking总结：http://www.jianshu.com/p/883fdda93a66

思路：DFS(backtracking) check
可以用visited数组，但这里因为元素确定是字母，所以直接inplace=表示visited。
实现a：直接dfs，每次进入递归再检查是否visited或出界
实现b：递归前就check是否visited，如果没有visit过，再递归去visit
这里因为是inplace=表示visited，相等check的判断已经包含了visited check。

Time Complexity: O(mn) Space Complexity: O(mn)

Solution1a Code：

class Solution {
    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(dfs_exist(board, row, col, word, 0))
                    return true;
            }
        return false;
    }
    
    private boolean dfs_exist(char[][] board, int i, int j, String word, int index) {
        
        // out of the boundary
        if(i < 0 || i > board.length - 1 || j < 0 || j > board[0].length - 1) return false;
        
        // not equal check (visisted check included)
        if(board[i][j] != word.charAt(index)) return false;
        
        if(index == word.length() - 1) return true;
        
        board[i][j] = '*'; // as visited
        
        boolean result = dfs_exist(board, i - 1, j, word, index + 1) ||
                         dfs_exist(board, i, j - 1, word, index + 1) ||
                         dfs_exist(board, i, j + 1, word, index + 1) ||
                         dfs_exist(board, i + 1, j, word, index + 1);
        // step back: restore
        board[i][j] = word.charAt(index);
        return result;
    }
}

Solution1b Code：

class Solution {
    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(dfs_exist(board, row, col, word, 0))
                    return true;
            }
        return false;
    }
    
    private boolean dfs_exist(char[][] board, int i, int j, String word, int index) {
        
        // not equal check
        if(board[i][j] != word.charAt(index)) return false;
    
        if(index == word.length() - 1) return true;
        
        board[i][j] = '*'; // as visited
        
        boolean result = false;
        if(i > 0 && board[i - 1][j] != '*') {
            result |= dfs_exist(board, i - 1, j, word, index + 1);
        }
        if(i < board.length - 1 && board[i + 1][j] != '*') {
            result |= dfs_exist(board, i + 1, j, word, index + 1);
        }
        if(j > 0 && board[i][j - 1] != '*') {
            result |= dfs_exist(board, i, j - 1, word, index + 1);
        }
        if(j < board[0].length - 1 && board[i][j + 1] != '*') {
            result |= dfs_exist(board, i, j + 1, word, index + 1);
        }
        
        // step back: restore
        board[i][j] = word.charAt(index);
        
        return result;
    }
}