5883. 判断单词是否能放入填字游戏内

题目

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

代码

  • 正序和反序对比
  • 枚举每行和每列中的空白区间
  • 核心在于比对已经填充过的单词
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;
    }
};
上一篇:leetcode 419甲板上的战舰


下一篇:java 控制台版五子棋