判断单词是否能放入填字游戏内

标签: 数组 枚举 矩阵

难度: Medium

给你一个 m x n 的矩阵 board ，它代表一个填字游戏 当前 的状态。填字游戏格子中包含小写英文字母（已填入的单词），表示 空 格的 ' ' 和表示 障碍 格子的 '#' 。

如果满足以下条件，那么我们可以 水平 （从左到右 或者 从右到左）或 竖直 （从上到下 或者 从下到上）填入一个单词：

  • 该单词不占据任何 '#' 对应的格子。
  • 每个字母对应的格子要么是 ' ' （空格）要么与 board 中已有字母 匹配 。
  • 如果单词是 水平 放置的，那么该单词左边和右边 相邻 格子不能为 ' ' 或小写英文字母。
  • 如果单词是 竖直 放置的，那么该单词上边和下边 相邻 格子不能为 ' ' 或小写英文字母。

给你一个字符串 word ，如果 word 可以被放入 board 中，请你返回 true ，否则请返回 false 。

示例 1：

输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc"
输出：true
解释：单词 "abc" 可以如上图放置（从上往下）。

示例 2：

输入：board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac"
输出：false
解释：无法放置单词，因为放置该单词后上方或者下方相邻格会有空格。

示例 3：

输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "ca"
输出：true
解释：单词 "ca" 可以如上图放置（从右到左）。

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m * n <= 2 * 105
  • board[i][j] 可能为 ' ' ，'#' 或者一个小写英文字母。
  • 1 <= word.length <= max(m, n)
  • word 只包含小写英文字母。

Submission

运行时间: 64 ms

内存: 50.2 MB

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        match = lambda x, y: all(a in [' ', b] for a, b in zip(x, y))
        for row in chain(board, zip(*board)):
            
            for ss in "".join(row).split('#'):
                if len(ss) == len(word) and (match(ss, word) or match(ss, word[::-1])):
                    return True
        return False
        #遍历行

Explain

此题解采用了直接匹配的策略，通过遍历填字游戏面板的所有行和列，并对每一行或列进行分析。首先，将面板的每一行和每一列合并处理，这通过使用 Python 的 chain 函数和 zip 函数完成。对于每一行或列，将其转化为字符串并用 '#' 分割，得到可能的放置单词的段。然后，检查每个段的长度是否与单词相等。若长度相等，则进一步检查该段是否可以通过从左向右或从右向左放置单词来与该段匹配。匹配函数 'match' 检查两个字符串中的每个相对应的字符位置，字符必须是空格或者相等才算匹配。如果找到匹配，返回 true。如果所有行和列都检查完毕仍未找到匹配，返回 false。

时间复杂度: O(m * n * k)

空间复杂度: O(max(m, n))

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        # 定义匹配函数，检查两个字符串是否可通过填充空格或匹配已有字符完成放置
        match = lambda x, y: all(a in [' ', b] for a, b in zip(x, y))
        # 遍历面板的所有行和列
        for row in chain(board, zip(*board)):
            # 将行或列转换成字符串，并以 '#' 分割，分割后的每部分代表一个可能的放置位置
            for ss in "".join(row).split('#'):
                # 检查每部分的长度是否与单词长度相等，并尝试匹配单词的正序与倒序
                if len(ss) == len(word) and (match(ss, word) or match(ss, word[::-1])):
                    return True
        # 如果所有可能的放置位置都不符合条件，则返回 false
        return False

Explore

在处理原始矩阵中的空白格和障碍格时，将每个空白格转换为字符' '（空格），而将障碍格转换为字符'#'。这样做的目的是为了在后续处理中，能够使用'#'来有效分割字符串，区分开不同的潜在放置位置。空白格作为可放置字母的位置保持为空格状态，以便在匹配函数中检查是否可以放置单词的某个字母。

使用'#'来分割字符串是一个有效的方法来区分连续的空白位置和障碍格。当字符串以'#'分割时，每个'#'都标识了一个障碍的结束和开始，这样连续的'#'会被视为单个分割点。因此，连续的空白位置（未被'#'隔断）将被视为一个完整的潜在单词放置区域，而多个连续的障碍格之间不会形成有效的放置区域，因为它们之间没有空白格。

在`match`函数中，当字符a是空格时，确实可以接受任何字符b作为匹配，这意味着单词的任何字母都可以放置在这个空白格中。这种设计符合填字游戏的规则，其中空白格是可以放置任何字母的。因此，这并不是“不正确”的放置，而是按照设计意图允许单词的任意字母填充到空白格中，前提是整个单词能完整匹配到指定的位置。