LeetCode 题解工作台
判断单词是否能放入填字游戏内
给你一个 m x n 的矩阵 board ，它代表一个填字游戏 当前 的状态。填字游戏格子中包含小写英文字母（已填入的单词），表示 空 格的 ' ' 和表示 障碍 格子的 '#' 。 如果满足以下条件，那么我们可以 水平 （从左到右 或者 从右到左）或 竖直 （从上到下 或者 从下到上）填入一个单词…
3
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·matrix
答案摘要
我们可以枚举矩阵的每个位置 $(i, j)$，判断是否能以该位置为起点，从左到右或从右到左放置单词 `word`，或者从上到下或从下到上放置单词 `word`。 该位置能作为起点需要满足以下条件：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·matrix 题型思路
题目描述
给你一个 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.lengthn == board[i].length1 <= m * n <= 2 * 105board[i][j]可能为' '，'#'或者一个小写英文字母。1 <= word.length <= max(m, n)word只包含小写英文字母。
解题思路
方法一：枚举
我们可以枚举矩阵的每个位置 ，判断是否能以该位置为起点，从左到右或从右到左放置单词 word，或者从上到下或从下到上放置单词 word。
该位置能作为起点需要满足以下条件：
- 如果要从从左到右放置单词
word，那么该位置必须是左边界，或者该位置左边的格子board[i][j - 1]是'#'； - 如果要从从右到左放置单词
word，那么该位置必须是右边界，或者该位置右边的格子board[i][j + 1]是'#'； - 如果要从从上到下放置单词
word，那么该位置必须是上边界，或者该位置上边的格子board[i - 1][j]是'#'； - 如果要从从下到上放置单词
word，那么该位置必须是下边界，或者该位置下边的格子board[i + 1][j]是'#'。
在满足上述条件的情况下，我们可以从该位置开始，判断是否能放置单词 word。我们设计一个函数 ，表示从位置 开始，沿着方向 放置单词 word 是否合法。如果合法，返回 true，否则返回 false。
函数 的实现如下：
我们先获取当前方向的另一个边界位置 ，即 ，其中 为单词 word 的长度。如果 在矩阵内，并且 的格子不是 '#'，则说明当前方向的另一个边界位置不是 '#'，因此不能放置单词 word，返回 false。
否则，我们从位置 开始，沿着方向 遍历单词 word，如果遇到格子 board[i][j] 不是空格或者不是单词 word 的当前字符，说明不能放置单词 word，返回 false。如果遍历完单词 word，说明能放置单词 word，返回 true。
时间复杂度 ，空间复杂度 。其中 和 分别为矩阵的行数和列数。
class Solution:
def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
def check(i, j, a, b):
x, y = i + a * k, j + b * k
if 0 <= x < m and 0 <= y < n and board[x][y] != '#':
return False
for c in word:
if (
i < 0
or i >= m
or j < 0
or j >= n
or (board[i][j] != ' ' and board[i][j] != c)
):
return False
i, j = i + a, j + b
return True
m, n = len(board), len(board[0])
k = len(word)
for i in range(m):
for j in range(n):
left_to_right = (j == 0 or board[i][j - 1] == '#') and check(i, j, 0, 1)
right_to_left = (j == n - 1 or board[i][j + 1] == '#') and check(
i, j, 0, -1
)
up_to_down = (i == 0 or board[i - 1][j] == '#') and check(i, j, 1, 0)
down_to_up = (i == m - 1 or board[i + 1][j] == '#') and check(
i, j, -1, 0
)
if left_to_right or right_to_left or up_to_down or down_to_up:
return True
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m _n_ L) where L is the word length, because each cell may be checked within its row and column. Space complexity is O(L) if temporary arrays are used to extract segments. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checking both directions is essential to pass all test cases.
- question_mark
Segmentation by '#' prevents invalid overlaps and ensures correctness.
- question_mark
Edge cases with single-cell gaps or pre-filled letters often catch naive solutions.
常见陷阱
外企场景- error
Ignoring reverse placements and only checking left-to-right or top-to-bottom.
- error
Overlooking segments shorter than the word length and attempting invalid matches.
- error
Not handling pre-filled letters that conflict with the word correctly.
进阶变体
外企场景- arrow_right_alt
Restrict word placement to only horizontal directions.
- arrow_right_alt
Allow diagonal placements in addition to horizontal and vertical.
- arrow_right_alt
Check for multiple words simultaneously and return all valid placements.