Solution Explanation: Check if Word Can Be Placed In Crossword

This problem asks whether a given word can be placed in a crossword puzzle board. The board contains empty spaces (' '), blocked cells ('#'), and possibly existing letters. The word can be placed horizontally (left-to-right or right-to-left) or vertically (top-to-bottom or bottom-to-top). The placement must adhere to these rules:

1. No '#' cells: The word cannot occupy any '#' cells.
2. Matching existing letters: Empty cells (' ') can be occupied. Existing letters must match the corresponding letter in the word.
3. Boundary conditions: If placed horizontally, there must be '#' or board boundaries on both sides of the word. The same applies vertically; there must be '#' or board boundaries above and below the word.

Approach: Enumeration and Boundary Check

The most efficient approach is to enumerate all possible starting positions and orientations of the word on the board and check for validity.

1. Iterate through board: The algorithm iterates through each cell of the board as a potential starting point for the word.

2. Check four orientations: For each starting position, it checks four possible orientations:

• Horizontal (left-to-right)
• Horizontal (right-to-left)
• Vertical (top-to-bottom)
• Vertical (bottom-to-top)

3. Boundary check: Before attempting placement, the algorithm checks if the chosen orientation respects boundary conditions. A word cannot be placed if there are empty spaces or letters adjacent to it in the direction of placement. For example, for horizontal placement, the cells immediately to the left and right of the starting position should be '#' or outside the board.

4. Character matching: The algorithm iterates through the letters of the word and checks if they match existing letters on the board or are placed in empty cells. If a mismatch occurs or a '#' cell is encountered, the current orientation is invalid.

5. Return true if valid placement is found: If any valid placement is found, the algorithm returns true. Otherwise, it returns false after checking all positions and orientations.

Time Complexity Analysis

• The outer loop iterates through all cells of the board, which takes O(m*n) time where 'm' is the number of rows and 'n' is the number of columns.
• For each cell, the algorithm checks four orientations.
• Checking each orientation involves iterating through the word (length 'k'), so this part takes O(k) time.
• Therefore, the overall time complexity is O(m * n * k).

Space Complexity Analysis

The algorithm uses a constant amount of extra space to store variables and function parameters. Therefore, the space complexity is O(1).

Code Implementation (Python)

def placeWordInCrossword(board, word):
    m, n = len(board), len(board[0])
    k = len(word)
 
    def is_valid(r, c, dr, dc):
        nr, nc = r + dr * k, c + dc * k
        if 0 <= nr < m and 0 <= nc < n and board[nr][nc] != '#':
            return False
        for i in range(k):
            curr_r, curr_c = r + i * dr, c + i * dc
            if not (0 <= curr_r < m and 0 <= curr_c < n):
                return False
            if board[curr_r][curr_c] != ' ' and board[curr_r][curr_c] != word[i]:
                return False
        return True
 
    for r in range(m):
        for c in range(n):
            if is_valid(r, c, 0, 1) or is_valid(r, c, 0, -1) or \
               is_valid(r, c, 1, 0) or is_valid(r, c, -1, 0):
                return True
    return False
 

The code in other languages (Java, C++, Go) follows a very similar structure, implementing the same logic with minor syntactic differences. The is_valid function encapsulates the checks for boundary conditions and character matching for a given position and orientation.