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

'''
算法原理
这个算法主要通过遍历棋盘的每一行和每一列，来检查是否可以放置给定的单词。它尝试了四种放置方式：
从左到右、从右到左、从上到下、从下到上。

水平检查:

对每一行进行检查。对于每一行中的非墙壁部分，检查单词是否可以从左到右或从右到左放置。如果当前格子与单词的对应字母不匹配，
或者超过了单词的长度，标记为不可行。
垂直检查:

对每一列进行类似的检查。对于每一列中的非墙壁部分，检查单词是否可以从上到下或从下到上放置。
边界条件:

在遍历时，算法考虑了墙壁的存在，以及单词的放置不能超出当前连续的非墙壁部分。
时间复杂度分析
空间复杂度:
空间复杂度为 O(1)，因为没有使用额外的空间（除了一些临时变量）。
时间复杂度:
水平和垂直检查每次都遍历整个棋盘，所以时间复杂度为 O(m * n * k)，其中 m 是行数，n 是列数，k 是单词的长度。
在最坏情况下，我们需要检查所有的行和列，因此整体复杂度是 O(m * n * k)。
该算法在处理大小为 m x n 的棋盘上具有较好的性能表现，特别是在 m * n 和 k 不过大的情况下。
'''
class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        # 获取棋盘的行数m和列数n，以及单词的长度k
        m, n = len(board), len(board[0])
        k = len(word)

        # 遍历每一行，尝试水平放置单词
        for i in range(m):
            row = board[i]
            j = 0
            while j < n:
                # 如果遇到墙壁 '#', 跳过当前格子
                if row[j] == '#':
                    j += 1
                    continue
                
                # 初始化 j0 为当前起始位置，ok1 和 ok2 为两个可能的匹配方向
                j0, ok1, ok2 = j, True, True

                # 遍历行中的连续非墙壁部分，检查是否可以放置单词
                while j < n and row[j] != '#':
                    # 检查单词从左到右放置是否匹配
                    if (j - j0 >= k) or (row[j] != ' ' and row[j] != word[j - j0]):
                        ok1 = False
                    
                    # 检查单词从右到左放置是否匹配
                    if (j - j0 >= k) or (row[j] != ' ' and row[j] != word[k - 1 - (j - j0)]):
                        ok2 = False
                    
                    j += 1
                
                # 如果任意一种方向匹配并且匹配的长度正好为k，则返回True
                if (ok1 or ok2) and j - j0 == k:
                    return True
                j += 1
        
        # 遍历每一列，尝试垂直放置单词
        for j in range(n):
            col = [row[j] for row in board]  # 获取第j列
            i = 0
            while i < m:
                # 如果遇到墙壁 '#', 跳过当前格子
                if col[i] == '#':
                    i += 1
                    continue
                
                # 初始化 i0 为当前起始位置，ok1 和 ok2 为两个可能的匹配方向
                i0, ok1, ok2 = i, True, True

                # 遍历列中的连续非墙壁部分，检查是否可以放置单词
                while i < m and col[i] != '#':
                    # 检查单词从上到下放置是否匹配
                    if (i - i0 >= k) or (col[i] != ' ' and col[i] != word[i - i0]):
                        ok1 = False
                    
                    # 检查单词从下到上放置是否匹配
                    if (i - i0 >= k) or (col[i] != ' ' and col[i] != word[k - 1 - (i - i0)]):
                        ok2 = False
                    
                    i += 1
                
                # 如果任意一种方向匹配并且匹配的长度正好为k，则返回True
                if (ok1 or ok2) and i - i0 == k:
                    return True
                j += 1
        
        # 如果没有找到合适的放置位置，则返回False
        return False

1176