Check if Word Can Be Placed In Crossword LeetCode solution in Python

1
class Solution:
2
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
3
        m, n = len(board), len(board[0])
4
        W = len(word)
5

6
        def valid(x, y):
7
            return 0 <= x < m and 0 <= y < n
8

9
        def place(x, y, word, direction):
10
            dx, dy = direction
11
            for c in word:
12
                if (
13
                    not valid(x, y)
14
                    or board[x][y] == "#"
15
                    or (board[x][y] != " " and board[x][y] != c)
16
                ):
17
                    return False
18
                x, y = x + dx, y + dy
19
            return True
20

21
        for x in range(m):
22
            for y in range(n):
23
                if board[x][y] == "#" or (
24
                    board[x][y] != " " and board[x][y] != word[0]
25
                ):
26
                    continue
27

28
                # left to right
29
                if (
30
                    (not valid(x, y - 1) or board[x][y - 1] == "#")
31
                    and (not valid(x, y + W) or board[x][y + W] == "#")
32
                    and place(x, y, word, [0, 1])
33
                ):
34
                    return True
35

36
                # right to left
37
                if (
38
                    (not valid(x, y + 1) or board[x][y + 1] == "#")
39
                    and (not valid(x, y - W) or board[x][y - W] == "#")
40
                    and place(x, y, word, [0, -1])
41
                ):
42
                    return True
43

44
                # top to bottom
45
                if (
46
                    (not valid(x - 1, y) or board[x - 1][y] == "#")
47
                    and (not valid(x + W, y) or board[x + W][y] == "#")
48
                    and place(x, y, word, [1, 0])
49
                ):
50
                    return True
51

52
                # bottom to top
53
                if (
54
                    (not valid(x + 1, y) or board[x + 1][y] == "#")
55
                    and (not valid(x - W, y) or board[x - W][y] == "#")
56
                    and place(x, y, word, [-1, 0])
57
                ):
58
                    return True
59

60
        return False