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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if Word Can Be Placed In Crossword

Number: 2146

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an m x n board representing the state of a crossword puzzle, determine if a given word can be placed on the board. Cells in the board may contain: • a lowercase English letter (from a solved word) • ' ' (empty cell) • '#' (blocked cell) A word can be placed horizontally (left to right or right to left) or vertically (top to bottom or bottom to top) if: • No letter is placed in a '#' cell. • Each cell used is either empty or already contains the same letter as in the word. • If placed horizontally, the cells immediately to the left and right of the word (if within board bounds) must be blocked ('#') or off the board. • If placed vertically, the cells immediately above and below the word (if within board bounds) must be blocked ('#') or off the board. The task is to return true if the word can be placed in any possible valid position according to the rules above; otherwise, return false.

Key Insights

  • Iterate over the board horizontally and vertically to identify continuous segments (slots) of cells that are not blocked.
  • For each identified candidate slot, check: • The length of the slot should match the word’s length. • Each cell in the slot must either be empty (' ') or already contain the matching letter. • The slot must be isolated: cells adjacent to the slot (left/right for horizontal, above/below for vertical) should not be part of an ongoing word (i.e. must be blocked or outside the board) to ensure a valid word placement.
  • Check both the original word and its reverse to account for placement in either direction.

Space and Time Complexity

Time Complexity: O(m * n * L) where m and n are board dimensions and L is the length of the word. We scan each cell and validate segments of length up to L. Space Complexity: O(1) extra space (not counting the input board and word).

Solution

We solve the problem by enumerating every potential slot in the board:

  1. For horizontal checks:
    • For each row, iterate over the columns and split the row into segments separated by '#'.
    • For each segment, verify if its length is equal to the word’s length.
    • Ensure that the segment is isolated from adjacent cells on its left and right (if any exist).
    • Check if for every position the board cell is either empty or equals the corresponding letter of the word. Also, check the reversed word.
  2. For vertical checks:
    • Similar to horizontal, iterate over each column and collect segments from consecutive rows, using '#' as delimiters.
    • Verify length, check adjacent boundaries (above and below), and validate the match for both orientations.
  3. If any segment satisfies the conditions, return true. Otherwise, return false after all possibilities have been exhausted. A key detail is verifying the boundaries before and after each segment to ensure that they are either blocked or off the board.

Code Solutions

# Python Code with line-by-line comments
def placeWordInCrossword(board, word):
    # Helper function to check if a segment matches the word (or its reverse)
    def check(segment, word):
        # If lengths do not match, return False immediately
        if len(segment) != len(word):
            return False
        # Check both normal and reversed order for placement
        for candidate in (word, word[::-1]):
            valid = True
            for i in range(len(segment)):
                # If board has a letter, it should match the candidate letter
                if segment[i] != ' ' and segment[i] != candidate[i]:
                    valid = False
                    break
            if valid:
                return True
        return False

    m, n = len(board), len(board[0])
    
    # Check horizontal placements
    for i in range(m):
        j = 0
        while j < n:
            # Skip blocked cells
            if board[i][j] == '#':
                j += 1
                continue
            start = j  # starting index of potential segment
            # Continue until a blocked cell is found or end of row reached
            while j < n and board[i][j] != '#':
                j += 1
            segment = board[i][start:j]
            # Check if the segment is valid isolated segment horizontally
            # Check left boundary: it must be at index 0 or previous cell is '#'
            left_bound = (start == 0 or board[i][start-1] == '#')
            # Check right boundary: it must be at end of row or next cell is '#'
            right_bound = (j == n or board[i][j] == '#')
            if left_bound and right_bound and check(segment, word):
                return True

    # Check vertical placements
    for j in range(n):
        i = 0
        while i < m:
            if board[i][j] == '#':
                i += 1
                continue
            start = i  # starting index of potential vertical segment
            while i < m and board[i][j] != '#':
                i += 1
            # Build the segment vertically as a list of characters
            segment = [board[k][j] for k in range(start, i)]
            # Check vertical boundaries: above and below must be valid
            top_bound = (start == 0 or board[start-1][j] == '#')
            bottom_bound = (i == m or board[i][j] == '#')
            if top_bound and bottom_bound and check(segment, word):
                return True

    return False

# Example usage:
board = [["#", " ", "#"],
         [" ", " ", "#"],
         ["#", "c", " "]]
word = "abc"
print(placeWordInCrossword(board, word))  # Expected output: True
← Back to All Questions