79. Word Search

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.

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.

Analysis:
6/6/2018 update:
这一遍居然忘了剪枝。。。直接调用4方向的dfs,比用dir 数组快得多 14ms.之前是21ms. 剪枝通常和检查处在同一个level上面。这道题的实现里面，检查是在dfs level,所以剪枝也是。一般基于树的dfs，检查和剪枝都在for 循环里面。

class Solution {
    int m;
    int n;
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0)
            return false;
        m = board.length;
        n = board[0].length;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dfs(board, word, 0, r, c)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int index, int r, int c) {
        if (index == word.length())
            return true;
       
        if (r < 0 || r >= m || c < 0|| c >= n || board[r][c] == '#' ||board[r][c] != word.charAt(index)) {
            return false;
        }
        board[r][c] = '#';
        boolean res = dfs(board, word, index + 1, r + 1, c) ||
            dfs(board, word, index + 1, r - 1, c)  ||
            dfs(board, word, index + 1, r, c + 1) ||
            dfs(board, word, index + 1, r, c - 1);
        board[r][c] = word.charAt(index);
        return res;
    }
}

--------------------------------------------------------------------------------------------------------------------------------------------

3/6/2018  update
Still want to figure out validate outside of loop. Since it is better to check the s.charAt(index) == board[x][y] outside loop, why not check everything outside. It's ugly to check s.charAt(index + 1) == board[newx][newy], cuz we dont know if index + 1 would out of range. 
----------------------------------------------------------------------------------------------------------------------------------------
DFS, remember to keep track of the path. 这道题我居然自己想出来用in-place的方式来记录path。越刷越有感觉了。

Why do we validate the value outside of loop? Because we want to apply the algorithm to the case when index == 0.

Solution:

class Solution {
    boolean res = false;
    int m,n;
    boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 
            || board[0].length == 0)
            return res;
        int[] dx = new int[]{0, 0,  1, -1};
        int[] dy = new int[]{1, -1, 0,  0};
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) {
                if (helper(board, word, i, j, 0, dx, dy)) {
                    return true;
                }
            }
        
        return false;
    }
    
    private boolean helper(char[][] board, 
                        String s, 
                        int x, 
                        int y, 
                        int index,
                        int[] dx,
                        int[] dy) {
        if (index == s.length()) {
            
            return true;
        }
        
        if (x < 0 || x >= m || y < 0 || y >= n || 
            board[x][y] != s.charAt(index) || board[x][y] == '#') return false;
        boolean res = false;
        char temp = board[x][y];
        board[x][y] = '#';
           for (int i = 0; i < 4; i++) {
            int newx = x + dx[i];
            int newy = y + dy[i];
            res = res || helper(board, s, newx, newy, index + 1, dx, dy);
            } 
        
       board[x][y] = temp;
        return res;
    }
}