生活随笔
收集整理的这篇文章主要介绍了
LeetCode 2018. 判断单词是否能放入填字游戏内（模拟）
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
文章目录
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
;if(flag
== 0){int j
= 0, len
= 0;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阿明），一起加油、一起学习进步！
创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖
总结
以上是生活随笔为你收集整理的LeetCode 2018. 判断单词是否能放入填字游戏内（模拟）的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
