判断单词是否能放入填字游戏内
难度:
标签:
题目描述
给你一个 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
只包含小写英文字母。
代码结果
运行时间: 64 ms, 内存: 50.2 MB
/*
* 思路:
* 1. 遍历board矩阵的每个位置,检查该位置是否可以作为单词的起点。
* 2. 对于每个起点,尝试水平和竖直两种方向放置单词。
* 3. 使用Java Stream处理二维数组。
* 4. 检查每个位置是否满足条件,如果满足,返回true。
* 5. 如果所有位置都不满足条件,返回false。
*/
import java.util.stream.IntStream;
public class Solution {
public boolean placeWordInCrossword(char[][] board, String word) {
int m = board.length, n = board[0].length;
char[] w = word.toCharArray();
return IntStream.range(0, m).boxed().flatMap(i ->
IntStream.range(0, n).mapToObj(j -> new int[]{i, j}))
.anyMatch(pos ->
canPlace(board, w, pos[0], pos[1], 0, 1) || canPlace(board, w, pos[0], pos[1], 0, -1) ||
canPlace(board, w, pos[0], pos[1], 1, 0) || canPlace(board, w, pos[0], pos[1], -1, 0));
}
private boolean canPlace(char[][] board, char[] word, int i, int j, int di, int dj) {
int m = board.length, n = board[0].length, k = 0;
while (i >= 0 && i < m && j >= 0 && j < n && k < word.length) {
if (board[i][j] != ' ' && board[i][j] != word[k]) return false;
i += di;
j += dj;
k++;
}
return k == word.length && (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == '#');
}
}
解释
方法:
此题解采用了直接匹配的策略,通过遍历填字游戏面板的所有行和列,并对每一行或列进行分析。首先,将面板的每一行和每一列合并处理,这通过使用 Python 的 chain 函数和 zip 函数完成。对于每一行或列,将其转化为字符串并用 '#' 分割,得到可能的放置单词的段。然后,检查每个段的长度是否与单词相等。若长度相等,则进一步检查该段是否可以通过从左向右或从右向左放置单词来与该段匹配。匹配函数 'match' 检查两个字符串中的每个相对应的字符位置,字符必须是空格或者相等才算匹配。如果找到匹配,返回 true。如果所有行和列都检查完毕仍未找到匹配,返回 false。
时间复杂度:
O(m * n * k)
空间复杂度:
O(max(m, n))
代码细节讲解
🦆
在将行或列的数据转换成字符串时,你是如何处理原始矩阵中的空白格和障碍格的?
▷🦆
你提到使用`#`来分割字符串以找到可能的单词放置位置,这种方法是否能准确区分连续的空白位置或者多个障碍格之间的区域?
▷🦆
函数`match`中,当字符a是空格时,任何b都被视为匹配。这是否意味着在某些情况下,单词的某些字母可以被不正确地放置在空白格中?
▷