原文链接: https://leetcode-cn.com/problems/check-if-word-can-be-placed-in-crossword

英文原文

You are given an m x n matrix board, representing the current state of a crossword puzzle. The crossword contains lowercase English letters (from solved words), ' ' to represent any empty cells, and '#' to represent any blocked cells.

A word can be placed horizontally (left to right or right to left) or vertically (top to bottom or bottom to top) in the board if:

• It does not occupy a cell containing the character '#'.
• The cell each letter is placed in must either be ' ' (empty) or match the letter already on the board.
• There must not be any empty cells ' ' or other lowercase letters directly left or right of the word if the word was placed horizontally.
• There must not be any empty cells ' ' or other lowercase letters directly above or below the word if the word was placed vertically.

Given a string word, return true if word can be placed in board, or false otherwise.

 

Example 1:

Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc"
Output: true
Explanation: The word "abc" can be placed as shown above (top to bottom).

Example 2:

Input: board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac"
Output: false
Explanation: It is impossible to place the word because there will always be a space/letter above or below it.

Example 3:

Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "ca"
Output: true
Explanation: The word "ca" can be placed as shown above (right to left). 

 

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m * n <= 2 * 105
• board[i][j] will be ' ', '#', or a lowercase English letter.
• 1 <= word.length <= max(m, n)
• word will contain only lowercase English letters.

中文题目

给你一个 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 只包含小写英文字母。

通过代码

高赞题解

遍历每一行和每一列，将两个 $\texttt$），我们要做的就是遍历（正序+倒序）每个槽位，判断 $\textit{word}$ 能否恰好填入该槽位。

时间复杂度：$O(nm)$。注意最内层循环与第二层循环共用同一个下标变量。

空间复杂度：$O(1)$。只需要常数的空间存放若干变量。

func placeWordInCrossword(board [][]byte, word string) bool {
	m, n, k := len(board), len(board[0]), len(word)
	// 遍历行
	for _, row := range board {
		for j := 0; j < n; j++ {
			if row[j] == '#' {
				continue
			}
			// 遍历并匹配两个 # 之间的字符
			j0, ok1, ok2 := j, true, true
			for ; j < n && row[j] != '#'; j++ { // 注意这里的 j 就是外层循环的 j，因此整体复杂度是线性的
				if j-j0 >= k || row[j] != ' ' && row[j] != word[j-j0] { // 正序匹配 word
					ok1 = false
				}
				if j-j0 >= k || row[j] != ' ' && row[j] != word[k-1-j+j0] { // 倒序匹配 word
					ok2 = false
				}
			}
			if (ok1 || ok2) && j-j0 == k { // 只要正序和倒序中有一个匹配成功，且两个 # 之间的字符长度恰好为 word 的长度，就返回 true
				return true
			}
		}
	}

	// 遍历列（同上）
	for j := 0; j < n; j++ {
		for i := 0; i < m; i++ {
			if board[i][j] == '#' {
				continue
			}
			i0, ok1, ok2 := i, true, true
			for ; i < m && board[i][j] != '#'; i++ {
				if i-i0 >= k || board[i][j] != ' ' && board[i][j] != word[i-i0] {
					ok1 = false
				}
				if i-i0 >= k || board[i][j] != ' ' && board[i][j] != word[k-1-i+i0] {
					ok2 = false
				}
			}
			if (ok1 || ok2) && i-i0 == k {
				return true
			}
		}
	}
	return false
}

统计信息

通过次数	提交次数	AC比率
2086	5087	41.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言