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:

1. It does not occupy a cell containing the character '#'.
2. The cell each letter is placed in must either be ' ' (empty) or match the letter already on the board.
3. There must not be any empty cells ' ' or other lowercase letters directly left or right of the word if the word was placed horizontally.
4. 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.

Example: board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc" Output: true (The word "abc" can be placed as shown above (top to bottom).)

How would you approach solving this problem efficiently? Consider the constraints:

• m == board.length
• n == board[i].length
• 1 <= m * n <= 2 * 10^5
• board[i][j] will be ' ', '#', or a lowercase English letter.
• 1 <= word.length <= max(m, n)
• word will contain only lowercase English letters.

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        word_len = len(word)

        def check_horizontal(row):  
            segments = ''.join(row).split('#')
            for segment in segments:
                if len(segment) == word_len:
                    valid = True
                    for i in range(word_len):
                        if segment[i] != ' ' and segment[i] != word[i]:
                            valid = False
                            break
                    if valid:
                        return True
                    
                    valid = True
                    for i in range(word_len):
                        if segment[i] != ' ' and segment[i] != word[word_len - 1 - i]:
                            valid = False
                            break
                    if valid:
                        return True
            return False

        def check_vertical(col):
            segments = ''.join(col).split('#')
            for segment in segments:
                if len(segment) == word_len:
                    valid = True
                    for i in range(word_len):
                        if segment[i] != ' ' and segment[i] != word[i]:
                            valid = False
                            break
                    if valid:
                        return True
                    
                    valid = True
                    for i in range(word_len):
                        if segment[i] != ' ' and segment[i] != word[word_len - 1 - i]:
                            valid = False
                            break
                    if valid:
                        return True
            return False

        # Check horizontal placements
        for row in board:
            if check_horizontal(row):
                return True

        # Check vertical placements
        for j in range(n):
            col = [board[i][j] for i in range(m)]
            if check_vertical(col):
                return True

        return False

Explanation:

The solution iterates through each row and column of the board, checking if the word can be placed horizontally or vertically. The check_horizontal and check_vertical functions split the row/column into segments based on the '#' character. Then, it verifies if any of these segments match the length of the word. If a segment matches the word's length, the function proceeds to check if the word can be placed either in its original order or in reverse order within that segment.

Time and Space Complexity:

Time Complexity:

• O(m * n * word_len), where m is the number of rows, n is the number of columns, and word_len is the length of the word. This is because we iterate through each row and column, and for each row/column, we iterate through the characters of the segments.

Space Complexity:

• O(max(m, n)), in the worst case. This space is utilized for temporary string segments during the splitting and checking processes. In the horizontal case it's O(n) and in the vertical case it's O(m).