题目
代码
- 正序和反序对比
- 枚举每行和每列中的空白区间
- 核心在于比对已经填充过的单词
class Solution {
public:
int m, n, t;
bool placeWordInCrossword(vector<vector<char>>& board, string word) {
// 判断一下二维数组中是否有长度为n的连续空白区域
t = word.size();
m = board.size();
n = board[0].size();
// 横着
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(board[i][j] == '#') continue;
int k = j;
bool ok1 = true, ok2 = true;
for(; j < n && board[i][j] != '#'; j++){
if(j - k >= t || (board[i][j] != ' ' && board[i][j] != word[j-k])) ok1 = false;
if(j - k >= t || (board[i][j] != ' ' && board[i][j] != word[t-1-j+k])) ok2 = false;
}
if((ok1 || ok2) && (j - k == t)){
return true;
}
}
}
//竖着
for(int j = 0; j < n; j++){
for(int i = 0; i < m; i++){
if(board[i][j] == '#') continue;
int k = i;
bool ok1 = true, ok2 = true;
for(; k < m && board[k][j] != '#'; k++){
if(k - i >= t || (board[k][j] != ' ' && board[k][j] != word[k-i])) ok1 = false;
if(k - i >= t || (board[k][j] != ' ' && board[k][j] != word[t-1-k+i])) ok2 = false;
}
if((ok1 || ok2) && (k - i == t)){
return true;
}
i = k;
}
}
return false;
}
};