FindWord.java

FindWord.java

class Solution {
    public boolean exist(char[][] board, String word) {
        if (word == null || word.length() == 0) return true;
        boolean[][] visited = new boolean[board.length][board.length];
        Character startChar = word.charAt(0);
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board.length; c++) {
                visited[r][c] = true;
                if (board[r][c] == startChar && backtracking(1, r, c, visited, board, word)) return true;
                visited[r][c] = false;
            }
        }
        
        return false;
    }
    
    private int[][] movements = {
        {-1, 0},
        {0, -1},
        {1, 0},
        {0, 1},
    };
    
    private boolean backtracking(int idx, int r, int c, boolean[][] visited, char[][] board, String word) {
        if (idx >= word.length()) return true;
        
        for (int[] movement: movements) {
            int tryRow = r + movement[0];
            int tryCol = c + movement[1];
            if (withinBounds(tryRow, tryCol, board)) {
                if (!visited[tryRow][tryCol] && board[tryRow][tryCol] == word.charAt(idx)) {
                    visited[tryRow][tryCol] = true;
                    if (backtracking(idx + 1, tryRow, tryCol, visited, board, word)) {
                        return true;
                    }
                    visited[tryRow][tryCol] = false;
                }
            }
        }
        
        return false;
    }
    
    private boolean withinBounds(int r, int c, char[][] board) {
        return r >= 0 && r < board.length && c >= 0 && c < board.length;
    }
}