题目

• 链接
• 考点：枚举+搜索+双指针

代码

• 正序和反序对比
• 枚举每行和每列中的空白区间
• 核心在于比对已经填充过的单词

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;
    }
};