79. Word Search

[LLancelot]

经典DFS题。

[LLancelot]

我的代码：

class Solution {
    private int w;
    private int h;
    
    public boolean exist(char[][] board, String word) {
        if (board.length == 0)
            return false;
        h = board.length;
        w = board[0].length;
        for (int i = 0; i < w; i++)
            for (int j = 0; j < h; j++)
                if (search(board, word, 0, i, j))
                    return true;
        return false;
    }
    
    public boolean search(char[][] board, String word, int pos, int x, int y){
        if (x<0 || x==w || y<0 || y==h || word.charAt(pos) != board[y][x])
            return false;
        if (pos == word.length() -1)
            return true;
        char cur = board[y][x];
        board[y][x] = 0;
        boolean find_every_dir = 
            search(board, word, pos+1, x+1, y)
            || search(board, word, pos+1, x-1, y)
            || search(board, word, pos+1, x, y+1)
            || search(board, word, pos+1, x, y-1);
        board[y][x] = cur;
        return find_every_dir;
    }
}