2018. Check if Word Can Be Placed In Crossword

Ｔ: O(mn*4*wordlength)
S: O(1)

class Solution {
    private static final int[][] DIR = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    public boolean placeWordInCrossword(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //  起點：" " or word[0]
                if (board[i][j] != ' ' && board[i][j] != word.charAt(0)) {
                    continue;
                }
                for (int[] dir : DIR) {
                    
                    int x = i - dir[0];
                    int y = j - dir[1];
                    // 起點的條件, 要在 boudary 或 ＃ 的旁邊, 所以這裡用減的去檢查是不是
                    // 起點的周邊有 boudary 或 ＃
                    if (in(board, x, y) && board[x][y] != '#') {
                        continue; 
                    }
                    // 確定是起點, 開始去找字符
                    if (findMatch(i, j, dir, board, word)) {
                        return true;
                    }
   
                }
            }
        }
        return false;
    }
    private boolean findMatch(int r, int c, int[] dir, char[][] board, String word) {
        int idx = 0;
        while (idx < word.length() && in(board, r, c)) {
            // 不在範圍內, return false
            if (!in(board, r, c)) {
                return false;
            }
            // 如果不是 空的可放的 並且 跟 word 也不相符,  return false
            if (board[r][c] != ' ' && board[r][c] != word.charAt(idx)) {
                return false;
            }
            idx++;
            r += dir[0];
            c += dir[1];
        }

        // 最後檢查 idx 是不是走完, 和最後 r, c 是不是在邊界或 # 上面
        if (idx == word.length() && (!in(board, r, c) || board[r][c] == '#')) {
            return true;  
        }
        return false;
    }
    public boolean in(char[][] board, int r, int c) {
        return r >= 0 && c >= 0 && r < board.length && c < board[0].length;
    }

}

/*
find starting point: 
1. " " or word[0]
2. around starting point is "#" or boundary

find match
match word
the match end+1 is "#" or boundary

Ｔ: O(mn*4*wordlength)
S: O(1)
*/