Check If Word Can Be Placed In Crossword - Leetcode Solution

Problem Description:

The task is to check if a given word can be placed in a crossword. A crossword is given as a 2D array of characters, where each cell may contain either a letter or a space. The word can be placed horizontally or vertically in the crossword. If the word can be placed, the function must return true, otherwise, it must return false.

Example:

Given the following crossword:

a b c d e f g h i j k l m n o p q r s t u

The word "dog" can be placed vertically, starting at row 3, column 2. The resulting crossword will be:

a b c d e f g h i j k d m n o o p q r s t u

Solution:

The problem can be solved by iterating over each cell in the crossword and checking if it is a space or if it contains the first letter of the word. If it is a space, we check if the word can be placed horizontally or vertically starting from that cell.

For example, if we are checking for the word "dog" in the above crossword, we first check if the cell at row 3, column 2 is a space or contains a "d". Since it contains a "d", we can try to place the word vertically starting at that cell.

To place the word vertically, we iterate over each cell below the starting cell, filling in the letters of the word as we go. If we reach the bottom of the crossword or if we encounter a non-space cell that does not match the corresponding letter of the word, we cannot place the word vertically at that position.

If we cannot place the word vertically, we try to place it horizontally starting from the same cell. To place the word horizontally, we iterate over each cell to the right of the starting cell, filling in the letters of the word as we go. If we reach the end of the crossword or if we encounter a non-space cell that does not match the corresponding letter of the word, we cannot place the word horizontally at that position.

If we cannot place the word horizontally or vertically at the starting cell, we move on to the next cell in the crossword and repeat the process.

If we have iterated over all cells in the crossword and have not found a valid position for the word, we return false.

The implementation of the solution involves checking each cell of the crossword and iterating over each cell below and to the right of the starting cell when trying to place the word vertically or horizontally, respectively. The code for the solution is shown below:

bool canPlaceWord(vector<vector<char>>& board, string word) { int m = board.size(); int n = board[0].size(); int len = word.size();

for(int i=0; i<m; i++) {
    for(int j=0; j<n; j++) {
        if(board[i][j] == ' ' || board[i][j] == word[0]) {
            // Vertical placement
            bool valid = true;
            if(i+len-1 < m) {
                for(int k=0; k<len; k++) {
                    char c = board[i+k][j];
                    if(c != ' ' && c != word[k]) {
                        valid = false;
                        break;
                    }
                }
                if(valid) return true;
            }
            // Horizontal placement
            valid = true;
            if(j+len-1 < n) {
                for(int k=0; k<len; k++) {
                    char c = board[i][j+k];
                    if(c != ' ' && c != word[k]) {
                        valid = false;
                        break;
                    }
                }
                if(valid) return true;
            }
        }
    }
}

return false;

}

The time complexity of the solution is O(mnlen), where m and n are the dimensions of the crossword and len is the length of the word. The space complexity is O(1) as the solution only uses constant extra space.

1