<p>You are given an <code>m x n</code> matrix <code>board</code>, representing the<strong> current </strong>state of a crossword puzzle. The crossword contains lowercase English letters (from solved words), <code>&#39; &#39;</code> to represent any <strong>empty </strong>cells, and <code>&#39;#&#39;</code> to represent any <strong>blocked</strong> cells.</p>

<p>A word can be placed<strong> horizontally</strong> (left to right <strong>or</strong> right to left) or <strong>vertically</strong> (top to bottom <strong>or</strong> bottom to top) in the board if:</p>

<ul>
	<li>It does not occupy a cell containing the character <code>&#39;#&#39;</code>.</li>
	<li>The cell each letter is placed in must either be <code>&#39; &#39;</code> (empty) or <strong>match</strong> the letter already on the <code>board</code>.</li>
	<li>There must not be any empty cells <code>&#39; &#39;</code> or other lowercase letters <strong>directly left or right</strong><strong> </strong>of the word if the word was placed <strong>horizontally</strong>.</li>
	<li>There must not be any empty cells <code>&#39; &#39;</code> or other lowercase letters <strong>directly above or below</strong> the word if the word was placed <strong>vertically</strong>.</li>
</ul>

<p>Given a string <code>word</code>, return <code>true</code><em> if </em><code>word</code><em> can be placed in </em><code>board</code><em>, or </em><code>false</code><em> <strong>otherwise</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/04/crossword-ex1-1.png" style="width: 478px; height: 180px;" />
<pre>
<strong>Input:</strong> board = [[&quot;#&quot;, &quot; &quot;, &quot;#&quot;], [&quot; &quot;, &quot; &quot;, &quot;#&quot;], [&quot;#&quot;, &quot;c&quot;, &quot; &quot;]], word = &quot;abc&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> The word &quot;abc&quot; can be placed as shown above (top to bottom).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/04/crossword-ex2-1.png" style="width: 180px; height: 180px;" />
<pre>
<strong>Input:</strong> board = [[&quot; &quot;, &quot;#&quot;, &quot;a&quot;], [&quot; &quot;, &quot;#&quot;, &quot;c&quot;], [&quot; &quot;, &quot;#&quot;, &quot;a&quot;]], word = &quot;ac&quot;
<strong>Output:</strong> false
<strong>Explanation:</strong> It is impossible to place the word because there will always be a space/letter above or below it.</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/10/04/crossword-ex3-1.png" style="width: 478px; height: 180px;" />
<pre>
<strong>Input:</strong> board = [[&quot;#&quot;, &quot; &quot;, &quot;#&quot;], [&quot; &quot;, &quot; &quot;, &quot;#&quot;], [&quot;#&quot;, &quot; &quot;, &quot;c&quot;]], word = &quot;ca&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> The word &quot;ca&quot; can be placed as shown above (right to left). 
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == board.length</code></li>
	<li><code>n == board[i].length</code></li>
	<li><code>1 &lt;= m * n &lt;= 2 * 10<sup>5</sup></code></li>
	<li><code>board[i][j]</code> will be <code>&#39; &#39;</code>, <code>&#39;#&#39;</code>, or a lowercase English letter.</li>
	<li><code>1 &lt;= word.length &lt;= max(m, n)</code></li>
	<li><code>word</code> will contain only lowercase English letters.</li>
</ul>

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        '''
        check every square, if it's empty try starting word there
        pick a direction (l, r, u, d) and continue that direction
            if we encounter a char not in word, return False
            if we encounter a square with a char, check if it == word[i]
                if yes, continue
                if not, return false
            if we encounter a "#"
                return false if i < len(word)
        when we reach i == len(word), check if square is out of bounds or "#"
            if so, return true
            else return false
        '''
        n_cols = len(board[0])
        n_rows = len(board)

        def backtrack(i, j, direction, word_left):
            di, dj = direction
            # Check completion
            if len(word_left) == 0:
                # The current index should be out of board or at #
                # Else word doesnt fit perfectly.
                if j < 0 or i < 0 or j == n_cols or i == n_rows or board[i][j] == "#":
                    return True

                return False
            
            # Check if cell can be filled with next letter
            if j == n_cols or j == -1 or i == -1 or i == n_rows or board[i][j] == "#":
                return False

            current_letter = board[i][j]

            # If current cell if with some other letter from the original board then we cant fill
            if current_letter != " " and current_letter != word_left[0]:
                return False

            # Add next letter
            board[i][j] = word_left[0]
            res = backtrack(i + di, j + dj, direction, word_left[1:])

            # we backtrack and return result
            board[i][j] = current_letter
        
            return res

        for i in range(n_rows):
            for j in range(n_cols):
                # In the direction of filling, no empty or filled element should be before the current cell.
                for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # Directions
                    if dj: # left / right
                        pre_j = j - dj # preceeding j is out of board or #
                        valid = pre_j < 0 or pre_j >= n_cols or board[i][pre_j] == "#"
                    if di: # move up / down    
                        pre_i = i - di # preceeding i is out of board or #
                        valid = pre_i < 0 or pre_i >= n_rows or board[pre_i][j] == "#"
                    if valid and backtrack(i, j, (di, dj), word):
                        return True

        return False

        # ROWS, COLS = len(board), len(board[0])
        # directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        # def validatePosition(r, c):
        #     if r >= ROWS or c >= COLS or r < 0 or c < 0 or board[r][c] == "#":
        #         return True
        #     else:
        #         return False

        # def dfs(r, c, i, direction):
        #     if i >= len(word):
        #         return validatePosition(r, c)
        #     if validatePosition(r, c):
        #         return False
            
        #     res = False
        #     if board[r][c] == " " or board[r][c] == word[i]:
        #         res = dfs(r + direction[0], c + direction[1], i + 1, direction)
        #         if res:
        #             return True
            
        #     return res

        # for r in range(ROWS):
        #     for c in range(COLS):
        #         if board[r][c] == "#":
        #             continue
        #         for direction in directions:
        #             if dfs(r, c, 0, direction) and validatePosition(r - direction[0], c - direction[1]):
        #                 return True
        
        # return False
1317