文章目录
1. 题目
给你一个 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 * 10^5
board[i][j] 可能为 ' ' ，'#' 或者一个小写英文字母。
1 <= word.length <= max(m, n)
word 只包含小写英文字母。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-if-word-can-be-placed-in-crossword
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
- 按题意模拟
class Solution {
int m, n;
public:
bool placeWordInCrossword(vector<vector<char>>& board, string word) {
m = board.size(), n = board[0].size();
for(int i = 0; i < m; ++i)
if(check(board, i, word, 0))
return true;
for(int j = 0; j < n; ++j)
if(check(board, j, word, 1))
return true;
return false;
}
bool check(vector<vector<char>>& b, int idx, string word, int flag)
{
unordered_map<int,char> cp;//记录board位置上的字符映射关系
if(flag == 0)
{
int j = 0, len = 0;//len记录board有效的字符长度
while(j < n)
{
if(b[idx][j] == '#' || j == n-1)
{ // 遇到结束符号
if(isalpha(b[idx][j]))
{
cp[len] = b[idx][j];
}
if(b[idx][j] != '#')
len++;
if(check(cp, len, word))
return true;
cp.clear();
len = 0;
}
else if(b[idx][j] == ' ')
len++;
else{
cp[len] = b[idx][j];
len++;
}
j++;
}
}
else
{
int i = 0, len = 0;
while(i < m)
{
if(b[i][idx] == '#' || i == m-1)
{
if(isalpha(b[i][idx]))
{
cp[len] = b[i][idx];
}
if(b[i][idx] != '#')
len++;
if(check(cp, len, word))
return true;
cp.clear();
len = 0;
}
else if(b[i][idx] == ' ')
len++;
else{
cp[len] = b[i][idx];
len++;
}
i++;
}
}
return false;
}
bool check(unordered_map<int,char> &cp, int len, string& word)
{
if(len != word.size())
return false;//长度不等，不能
if(cp.size() == 0) return true;
bool flag1 = true, flag2 = true;//正反顺序都可以进行检查
for(auto& x : cp)
{
if(word[x.first] != x.second)//正序
{
flag1 = false;
break;
}
}
if(flag1) return true;
for(auto& x : cp)
{
if(word[len-1-x.first] != x.second) // 逆序检查
{
flag2 = false;
break;
}
}
return flag2;
}
};
336 ms 414.9 MB C++
我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！