lc-79

//Given an m x n grid of characters board and a string word, return true if word
// exists in the grid. 
//
// The word can be constructed from letters of sequentially adjacent cells, wher
//e adjacent cells are horizontally or vertically neighboring. The same letter cel
//l may not be used more than once. 
//
// 
// Example 1: 
//
// 
//Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
// "ABCCED"
//Output: true
// 
//
// Example 2: 
//
// 
//Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
// "SEE"
//Output: true
// 
//
// Example 3: 
//
// 
//Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word =
// "ABCB"
//Output: false
// 
//
// 
// Constraints: 
//
// 
// m == board.length 
// n = board[i].length 
// 1 <= m, n <= 6 
// 1 <= word.length <= 15 
// board and word consists of only lowercase and uppercase English letters. 
// 
//
// 
// Follow up: Could you use search pruning to make your solution faster with a l
//arger board? 
// Related Topics Array Backtracking Matrix 
// 👍 10362 👎 389


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean exist(char[][] board, String word) {
        if (board == null) {
            return false;
        }

        boolean[][] used = new boolean[board.length][];
        for (int i = 0; i < board.length; i++) {
            used[i] = new boolean[board[i].length];
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                used[i][j] = true;
                if (existFunc(board, used, word, 0, i, j)) {
                    return true;
                }
                used[i][j] = false;
            }
        }
        return false;
    }

    private boolean existFunc(char[][] board, boolean[][] used, String word, int index, int i, int j) {
        if (board[i][j] != word.charAt(index)) {
            return false;
        }

        if (index == word.length() - 1) {
            return true;
        }

        boolean left = false, right = false, up = false, down = false;
        if (i > 0 && !used[i - 1][j]) {
            used[i - 1][j] = true;
            up = existFunc(board, used, word, index + 1, i - 1, j);
            used[i - 1][j] = false;
        }
        if (i < board.length - 1 && !used[i + 1][j]) {
            used[i + 1][j] = true;
            down = existFunc(board, used, word, index + 1, i + 1, j);
            used[i + 1][j] = false;
        }
        if (j > 0 && !used[i][j - 1]) {
            used[i][j - 1] = true;
            left = existFunc(board, used, word, index + 1, i, j - 1);
            used[i][j - 1] = false;
        }
        if (j < board[0].length - 1 && !used[i][j + 1]) {
            used[i][j + 1] = true;
            right = existFunc(board, used, word, index + 1, i, j + 1);
            used[i][j + 1] = false;
        }

        return left || right || up || down;
    }
}
//leetcode submit region end(Prohibit modification and deletion)