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.



Solution:

Intuitively, DFS is a good choice to solve this problem.

Form any point, we use DFS, recursively find if the character in every position matches the target.

When we go to a next level, we set the current position "visited" to avoid cycle.



Code:

public class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0) {
            return false;
        }
        if (board[0] == null || board[0].length == 0) {
            return false;
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfs(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] board, String word, int i, int j, int pos) {
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
            return false;
        }
        if (board[i][j] != word.charAt(pos)) {
            return false;
        }
        if (pos == word.length() - 1) {
            return true;
        }
        
        board[i][j] = '#';
        
        boolean result = dfs(board, word, i - 1, j, pos + 1) || 
                         dfs(board, word, i + 1, j, pos + 1) || 
                         dfs(board, word, i, j - 1, pos + 1) || 
                         dfs(board, word, i, j + 1, pos + 1);
        
        board[i][j] = word.charAt(pos);
        return result;
    }
}