leetcode
leetcode 1801 ~ 1850
判断单词是否能放入填字游戏内

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

难度:

标签:

题目描述

给你一个 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都被视为匹配。这是否意味着在某些情况下,单词的某些字母可以被不正确地放置在空白格中?
在`match`函数中,当字符a是空格时,确实可以接受任何字符b作为匹配,这意味着单词的任何字母都可以放置在这个空白格中。这种设计符合填字游戏的规则,其中空白格是可以放置任何字母的。因此,这并不是“不正确”的放置,而是按照设计意图允许单词的任意字母填充到空白格中,前提是整个单词能完整匹配到指定的位置。

相关问题