[Leetcode] 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 =

[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]

word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
DFS题目，注意的地方在于剪枝，我们可以构建一个word的前缀表，当我们dfs的时候发现当前的字符串不在这个前缀表中，那么直接return false避免不必要的递归。另一方面，在遍历每一个棋盘的起始位置的时候，注意起始状态不要写错了，按照我的dfs写法，起始状态就是当前的这个字符而不是空串。

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
 public boolean exist(char[][] board, String word) {
     if(word == null) return false;
     HashSet<String> set = new HashSet<String>();
     for(int i = 1; i < word.length(); i++) set.add(word.substring(0, i));
     int m = board.length;
     if(m == 0) return false;
     int n = board[0].length;
     boolean[][] marked = new boolean[m][n];
     for(int i = 0; i < m; i++) {
         for(int j = 0; j < n; j++) {
             marked[i][j] = true;
             if(dfs(board, word, ""+board[i][j], marked, i, j, set)) return true;
             marked[i][j] = false;
         }
     }
     return false;
 }
    
    private boolean dfs(char[][] board, String word, String current, boolean[][] marked, int x, int y, HashSet<String> set) {
        int m = board.length;
        int n = board[0].length;
        if(word.equals(current)) return true;
        if(set.contains(current) == false) return false;
        
        for(int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i];
            if(xx >= 0 && xx < m && yy >= 0 && yy < n && marked[xx][yy] == false) {
                marked[xx][yy] = true;
                if(dfs(board, word, current+board[xx][yy], marked, xx, yy, set)) return true;
                marked[xx][yy] = false;
            }
        }
        
        return false;
    }