You are given an $m \times n$ matrix board representing a crossword puzzle and a string word. Each cell in board can be an empty space ' ', a barrier '#', or a lowercase English letter.

A word can be placed horizontally from left to right or right to left, or vertically from top to bottom or bottom to top, if and only if:

• It can be placed in a contiguous sequence of cells of length exactly equal to word.length.

• The sequence of cells must be completely bounded by the grid boundaries or '#' cells on both ends.

• For each position in the sequence, the cell is either an empty space ' ' or contains the exact same letter as the corresponding character in word.

Return true if word can be placed anywhere in board, or false otherwise.

Constraints:

• m $==$ board.length

• n $==$ board[i].length

• $1 \leq m \times n \leq 2 \times 10^5$

• board[i][j] is ' ', '#', or a lowercase English letter.

• $1 \leq$ word.length $\leq \max(m, n)$

• word consists only of lowercase English letters.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.