Check if Word Can Be Placed In Crossword

Medium

Asked by:

19 views

Topics:

ArraysStrings

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.

Example 1:

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

Example 2:

Input: board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac"
Output: false
Explanation: It is impossible to place the word because there will always be a space/letter above or below it.

Example 3:

Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "ca"
Output: true
Explanation: The word "ca" can be placed as shown above (right to left).

Constraints:

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the crossword board (rows and columns), and what is the maximum length of the word?
What characters can appear in the crossword board? Is it limited to lowercase letters, or are other characters (e.g., uppercase, numbers, special symbols) possible?
If the word can be placed in multiple locations or orientations, should I return `true` as soon as I find one, or do I need to find all possible placements?
Is the crossword board guaranteed to be rectangular (all rows have the same length), and is the word guaranteed to be non-empty?
What should I return if the board or the word are null or empty strings?

Brute Force Solution

Approach

The brute force approach for this problem is all about trying every possible placement of the word in the crossword. We will explore every location and orientation to see if the word fits and matches existing letters.

Here's how the algorithm would work step-by-step:

First, consider placing the word horizontally, starting from the very top-left corner of the crossword.
Check if the word fits within the bounds of the crossword when placed horizontally at that location.
Also, check if each letter of the word matches the existing letters in the crossword at that location, or if the crossword square is empty.
If the word fits and all letters match or the squares are empty, we have found a valid placement, so we can stop. If it doesn't fit or there's a mismatch, try the next horizontal location to the right.
Keep shifting the starting position one square at a time to the right, checking the fit and letter matches for each new position on the top row.
Once you reach the end of the first row, move to the second row and repeat the process of trying every horizontal position on that row.
Continue this process for every row in the crossword, until you've tried every possible horizontal position.
Now, repeat the entire process but this time consider placing the word vertically instead of horizontally.
Check the fit, letter matches, and try every possible vertical starting position in the crossword.
If, after trying all horizontal and vertical positions, you still haven't found a valid placement, the word cannot be placed in the crossword.

Code Implementation

def can_place_word_in_crossword(board, word):
    rows = len(board)
    cols = len(board[0])
    word_length = len(word)

    # Check horizontal placement
    for row_index in range(rows):
        for col_index in range(cols - word_length + 1):
            valid = True

            # Check if word fits and matches
            for word_index in range(word_length):
                if board[row_index][col_index + word_index] != ' ' and \
                   board[row_index][col_index + word_index] != word[word_index]:
                    valid = False
                    break

            if valid:
                return True

    # Check vertical placement
    for row_index in range(rows - word_length + 1):
        for col_index in range(cols):
            valid = True

            # Check if word fits and matches
            for word_index in range(word_length):
                if board[row_index + word_index][col_index] != ' ' and \
                   board[row_index + word_index][col_index] != word[word_index]:
                    valid = False
                    break

            if valid:
                return True

    # No valid placement found
    return False

Big(O) Analysis

Time Complexity

O(m * n * l) – Let m be the number of rows in the crossword, n be the number of columns, and l be the length of the word to be placed. The algorithm iterates through each cell in the m x n crossword grid as a potential starting position for the word. For each starting position, it checks if the word fits horizontally and vertically. In each of these directions, it compares each of the l letters in the word with the corresponding cell in the crossword. Thus, the time complexity is driven by iterating through all m * n cells and, for each cell, performing up to l comparisons. Therefore the time complexity is O(m * n * l).

Space Complexity

O(1) – The provided brute force approach iterates through the crossword grid to find a suitable placement for the word. It primarily uses loop indices and comparison operations which require constant extra space. No additional data structures like arrays, hash maps, or recursion stacks are created to store intermediate results or visited locations. Therefore, the space complexity remains constant regardless of the crossword's size (rows * cols) or the word's length.

Optimal Solution

Approach

The task is to check if a given word can be placed into a crossword puzzle. The optimal strategy involves checking possible locations and directions for the word, ensuring it fits within the crossword's boundaries and matches existing letters where applicable. We'll focus on quickly eliminating invalid placements to find a valid one efficiently.

Here's how the algorithm would work step-by-step:

First, find all possible starting positions for the word within the crossword grid. A starting position is valid if it is within the bounds of the grid.
For each starting position, consider both horizontal and vertical directions for placing the word.
For each starting position and direction, check if the word fits entirely within the crossword's boundaries in that direction.
Next, verify if the word can be placed without conflicting with existing letters. If the crossword already has a letter in a position where you want to place the word, make sure the letters match. If they don't match, that position and direction are invalid.
If all checks pass (fits within boundaries and matches existing letters), then the word can be placed in the crossword. Return true.
If you've checked all possible starting positions and directions and haven't found a valid placement, the word cannot be placed. Return false.

Code Implementation

def can_place_word_in_crossword(crossword, word):
    rows = len(crossword)
    cols = len(crossword[0])
    word_length = len(word)

    for start_row in range(rows):
        for start_col in range(cols):
            # Check horizontal placement
            if can_place_horizontally(crossword, word, start_row, start_col):
                return True

            # Check vertical placement
            if can_place_vertically(crossword, word, start_row, start_col):
                return True

    return False

def can_place_horizontally(crossword, word, start_row, start_col):
    cols = len(crossword[0])
    word_length = len(word)

    # Check if the word fits within bounds
    if start_col + word_length > cols:
        return False

    for i in range(word_length):
        # Check if letters match or space is empty
        cell = crossword[start_row][start_col + i]
        if cell != ' ' and cell != word[i]:
            return False

    return True

def can_place_vertically(crossword, word, start_row, start_col):
    rows = len(crossword)
    word_length = len(word)

    # Check if the word fits within bounds
    if start_row + word_length > rows:
        return False

    for i in range(word_length):
        # Check if letters match or space is empty
        cell = crossword[start_row + i][start_col]
        if cell != ' ' and cell != word[i]:
            return False

    return True

Big(O) Analysis

Time Complexity

O(m * n * l) – Let m be the number of rows in the crossword, n be the number of columns in the crossword, and l be the length of the word. The algorithm iterates through each cell in the crossword grid (m * n) to find potential starting positions. For each starting position, it checks both horizontal and vertical directions (constant time, so we can ignore this multiplicative factor of 2). For each direction, it iterates at most 'l' times to verify boundary conditions and letter conflicts. Therefore, the overall time complexity is approximately O(m * n * l).

Space Complexity

O(1) – The algorithm's space complexity is determined by the variables used within the loops and conditional checks. No additional data structures, like lists or hash maps, are created to store intermediate results or visited locations. The algorithm primarily uses a few constant space variables for indexing and comparison, independent of the crossword grid's dimensions or the word's length. Therefore, the auxiliary space used is constant, regardless of the input size N (where N could represent the dimensions of the crossword or the length of the word).

Edge Cases

Case	How to Handle
Null or empty crossword or word input	Return false immediately as a valid placement is impossible.
Word length is greater than any dimension of the crossword	Return false, as the word cannot fit in either direction.
Crossword contains invalid characters (not ' ' or letter)	Throw an IllegalArgumentException or return false after validation.
Word contains invalid characters (not letters)	Throw an IllegalArgumentException or return false after validation.
Crossword is a single row or column	The algorithm should still correctly check if the word can be placed horizontally or vertically, respectively.
Multiple possible placements exist	The problem only asks to check if a valid placement exists, so return true as soon as one is found.
Word contains consecutive repeating characters	The algorithm should correctly handle consecutive identical letters in both the word and the crossword.
Crossword is very large, causing potential performance issues	Optimize the search by immediately returning when a valid placement is found, avoiding unnecessary iterations.

Null or empty crossword or word input

How to Handle:

Return false immediately as a valid placement is impossible.

Word length is greater than any dimension of the crossword

How to Handle:

Return false, as the word cannot fit in either direction.

Crossword contains invalid characters (not ' ' or letter)

How to Handle:

Throw an IllegalArgumentException or return false after validation.

Word contains invalid characters (not letters)

How to Handle:

Throw an IllegalArgumentException or return false after validation.

Crossword is a single row or column

How to Handle:

The algorithm should still correctly check if the word can be placed horizontally or vertically, respectively.

Multiple possible placements exist

How to Handle:

The problem only asks to check if *a* valid placement exists, so return true as soon as one is found.

Word contains consecutive repeating characters

How to Handle:

The algorithm should correctly handle consecutive identical letters in both the word and the crossword.

Crossword is very large, causing potential performance issues

How to Handle:

Optimize the search by immediately returning when a valid placement is found, avoiding unnecessary iterations.