2018. Check if Word Can Be Placed In Crossword

You are given an m x n matrix board, representing the current state of a crossword puzzle. The crossword contains lowercase English letters (from solved words), ‘ ‘ to represent any empty cells, and ‘#’ to represent any blocked cells.

A word can be placed horizontally (left to right or right to left) or vertically (top to bottom or bottom to top) in the board if:

• It does not occupy a cell containing the character ‘#’.
• The cell each letter is placed in must either be ‘ ‘ (empty) or match the letter already on the board.
• There must not be any empty cells ‘ ‘ or other lowercase letters directly left or right of the word if the word was placed horizontally.
• There must not be any empty cells ‘ ‘ or other lowercase letters directly above or below the word if the word was placed vertically.

Given a string word, return true if word can be placed in board, or false otherwise.

c++

class Solution {
    int n, m;
    bool checkHorizon(vector<vector<char>>& board, string& w, int y, int x) {
        if(x > m - w.length()) return false;
        int countLen = 0;
        bool res = true;
        for(int i = x; i < m and board[y][i] != '#'; i++, countLen++) {
            if(countLen < w.length()) {
                if(board[y][i] != ' ' and board[y][i] != w[i-x]) res = false;
            } else return false;
        }

        if(countLen != w.length()) return false;
        if(res) return true;

        for(int i = x + w.length() - 1, j = 0; i >= x; i--,j++) {
            if(board[y][i] != ' ' and board[y][i] != w[j]) return false;
        }
        return true;
    }

    bool checkVertical(vector<vector<char>>& board, string& w, int y, int x) {
        if(y > n - w.length()) return false;
        int countLen = 0;
        bool res = true;
        for(int i = y; i < n and board[i][x] != '#'; i++, countLen++) {
            if(countLen < w.length()) {
                if(board[i][x] != ' ' and board[i][x] != w[i-y]) res = false;
            } else return false;
        }

        if(countLen != w.length()) return false;
        if(res) return true;

        for(int i = y + w.length() - 1, j = 0; i >= y; i--,j++) {
            if(board[i][x] != ' ' and board[i][x] != w[j]) return false;
        }
        return true;
    }
public:
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        n = board.size(), m = board[0].size();
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == '#') continue;
                if((!j or board[i][j-1] == '#') and checkHorizon(board, word, i, j)) return true;
                if((!i or board[i-1][j] == '#') and checkVertical(board, word, i, j)) return true;
            }
        }

        return false;
    }
};