<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>

def check_down(r,c,rows,cols,board, word) -> bool:
    # check above cell
    if r-1 in range(rows) and c in range(cols):
        if board[r-1][c] == " ": return False
        if board[r-1][c] != "#": return False    
    
    # iterate through word
    for i in range(len(word)):
        # out of bound
        if not(r in range(rows) and c in range(cols)):
            return False

        if board[r][c] == "#": 
            return False
        if board[r][c] != " " and board[r][c] != word[i]:
            return False
        
        # update r and c
        r += 1
    
    # check below cell    
    if not (r in range(rows)): 
        return True
    elif board[r][c] == "#": 
        return True
    else:
        return False
    
def check_up(r,c,rows,cols,board, word) -> bool:
    # check below cell
    if r+1 in range(rows) and c in range(cols):
        if board[r+1][c] == " ": return False
        if board[r+1][c] != "#": return False    
    
    # iterate through word
    for i in range(len(word)):
        # out of bound
        if not(r in range(rows) and c in range(cols)):
            return False

        if board[r][c] == "#": 
            return False
        if board[r][c] != " " and board[r][c] != word[i]:
            return False
        
        # update r and c
        r -= 1
    
    # check above cell    
    if not (r in range(rows)): 
        return True
    elif board[r][c] == "#": 
        return True
    else:
        return False
    
def check_right(r,c,rows,cols,board, word) -> bool:
    # check left-one cell
    if r in range(rows) and c-1 in range(cols):
        if board[r][c-1] == " ": return False
        if board[r][c-1] != "#": return False    
    
    # iterate through word
    for i in range(len(word)):
        # out of bound
        if not(r in range(rows) and c in range(cols)):
            return False

        if board[r][c] == "#": 
            return False
        if board[r][c] != " " and board[r][c] != word[i]:
            return False
        
        # update r and c
        c += 1
    
    # check right-one cell    
    if not (c in range(cols)): 
        return True
    elif board[r][c] == "#": 
        return True
    else:
        return False
    
def check_left(r,c,rows,cols,board, word) -> bool:
    # check right-one cell
    if r in range(rows) and c+1 in range(cols):
        if board[r][c+1] == " ": return False
        if board[r][c+1] != "#": return False    
    
    # iterate through word
    for i in range(len(word)):
        # out of bound
        if not(r in range(rows) and c in range(cols)):
            return False

        if board[r][c] == "#": 
            return False
        if board[r][c] != " " and board[r][c] != word[i]:
            return False
        
        # update r and c
        c -= 1
    
    # check left-one cell    
    if not (c in range(cols)): 
        return True
    elif board[r][c] == "#": 
        return True
    else:
        return False
        

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        """10:38pm
        finish: 11:09pm 31mins
        
        def check_down(r,c,board):
            # check above cell
            if above cell is blank or contains letter: return False
            
            for i in range(word):
                if r out of bound or c out of bound: return False
                if board[r][c] == "#": return False
                if board[r][c] != word[i]: return False
                if board[r][c] == word[i] or board[r][c] == " ": continue
            
            if next_r or next_c out of bound: return True
            if next cell is "#": return True
            else:
                return False                
        """
        rows = len(board)
        cols = len(board[0])
        
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == " " or board[r][c] == word[0]:
                    checkDown = check_down(r,c,rows,cols,board, word)
                    checkUp = check_up(r,c,rows,cols,board, word)
                    checkLeft = check_left(r,c,rows,cols,board, word)
                    checkRight = check_right(r,c,rows,cols,board, word)
                    if checkDown or checkUp or checkLeft or checkRight:
                        return True
        return False
1328