We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Check if Word Can Be Placed In Crossword

Difficulty: Medium

Problem Description

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.

Key Insights

  • The board can have empty spaces, blocked cells, and filled letters.
  • The word can be placed in four possible orientations: horizontally (left to right and right to left) and vertically (top to bottom and bottom to top).
  • We need to ensure that there are no adjacent filled cells or empty spaces in the direction of the word placement.

Space and Time Complexity

Time Complexity: O(m * n) - We may need to check each cell in the board for potential placement. Space Complexity: O(1) - We use only a few variables to keep track of the current position and checks.

Solution

To solve the problem, we will:

  1. Iterate through every cell in the board.
  2. For each empty cell, check if a word can be placed horizontally and vertically.
  3. For each orientation, validate that:
    • The cells occupied by the word do not contain blocked cells ('#').
    • The surrounding cells do not contain filled letters or empty cells that would invalidate the placement.
  4. If a valid placement is found, return true; otherwise, return false after checking all cells.

Code Solutions

def canPlaceWord(board, word):
    m, n = len(board), len(board[0])
    word_len = len(word)

    def canPlaceHorizontally(r, c):
        if c > 0 and board[r][c - 1] != '#':
            return False
        if c + word_len < n and board[r][c + word_len] != '#':
            return False
        for i in range(word_len):
            if board[r][c + i] != ' ' and board[r][c + i] != word[i]:
                return False
        return True

    def canPlaceVertically(r, c):
        if r > 0 and board[r - 1][c] != '#':
            return False
        if r + word_len < m and board[r + word_len][c] != '#':
            return False
        for i in range(word_len):
            if board[r + i][c] != ' ' and board[r + i][c] != word[i]:
                return False
        return True

    for r in range(m):
        for c in range(n):
            if board[r][c] == ' ':
                if c + word_len <= n and canPlaceHorizontally(r, c):
                    return True
                if r + word_len <= m and canPlaceVertically(r, c):
                    return True
    return False
← Back to All Questions