#2018

Medium

LeetCode Problem Workspace

Check if Word Can Be Placed In Crossword

Determine if a word fits in a crossword grid using array and matrix checks, accounting for spaces, letters, and blocked cells.

array matrix enumeration

Problem Statement

You are given an m x n grid representing a crossword puzzle. Cells may contain lowercase letters, empty spaces as ' ', or blocked cells as '#'. Determine whether a given word can be placed on the board according to crossword rules.

The word can be placed horizontally (left to right or right to left) or vertically (top to bottom or bottom to top) if it fits in consecutive empty or matching letter cells without overlapping blocked cells. Return true if the word can be placed in any valid position, otherwise return false.

Examples

Example 1

Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc"

Output: true

The word "abc" can be placed as shown above (top to bottom).

Example 2

Input: board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac"

Output: false

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

The word "ca" can be placed as shown above (right to left).

Constraints

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

Solution Approach

Scan rows and columns

Iterate through each row and column segment separated by '#' and check if the segment length matches the word length. Reverse the segment to check for backward placements and ensure letters match or are empty.

Validate placement

For each candidate segment, compare the word character by character. Any mismatch with a pre-filled letter invalidates the segment. Only fully matching or empty segments are accepted.

Return result

If any valid segment allows the word to fit in any direction, return true. If no segment matches after scanning all rows and columns, return false.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n L) where L is the word length, because each cell may be checked within its row and column. Space complexity is O(L) if temporary arrays are used to extract segments.

What Interviewers Usually Probe

Checking both directions is essential to pass all test cases.
Segmentation by '#' prevents invalid overlaps and ensures correctness.
Edge cases with single-cell gaps or pre-filled letters often catch naive solutions.

Common Pitfalls or Variants

Common pitfalls

Ignoring reverse placements and only checking left-to-right or top-to-bottom.
Overlooking segments shorter than the word length and attempting invalid matches.
Not handling pre-filled letters that conflict with the word correctly.

Follow-up variants

Restrict word placement to only horizontal directions.
Allow diagonal placements in addition to horizontal and vertical.
Check for multiple words simultaneously and return all valid placements.

FAQ

What does 'Check if Word Can Be Placed In Crossword' require?

You need to determine if a given word fits in a board segment considering empty spaces, letters, and blocked cells in all directions.

Can the word be placed backwards or upwards?

Yes, valid placement includes left-to-right, right-to-left, top-to-bottom, and bottom-to-top directions.

How do I handle pre-filled letters in the crossword?

Compare each word character with the cell; if it is a letter, it must match exactly; otherwise, the placement is invalid.

What pattern does this problem follow?

It follows the Array plus Matrix pattern where row and column enumeration and segmentation are critical.

What is a common mistake when solving this problem?

Many solutions fail to check reverse placements or segments separated by blocked cells, leading to incorrect false results.

terminal

Solution

Solution 1: Enumeration

We can enumerate each position $(i, j)$ in the matrix, and judge whether we can place the word `word` from left to right or from right to left, or from top to bottom or from bottom to top, starting from this position.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        def check(i, j, a, b):
            x, y = i + a * k, j + b * k
            if 0 <= x < m and 0 <= y < n and board[x][y] != '#':
                return False
            for c in word:
                if (
                    i < 0
                    or i >= m
                    or j < 0
                    or j >= n
                    or (board[i][j] != ' ' and board[i][j] != c)
                ):
                    return False
                i, j = i + a, j + b
            return True

        m, n = len(board), len(board[0])
        k = len(word)
        for i in range(m):
            for j in range(n):
                left_to_right = (j == 0 or board[i][j - 1] == '#') and check(i, j, 0, 1)
                right_to_left = (j == n - 1 or board[i][j + 1] == '#') and check(
                    i, j, 0, -1
                )
                up_to_down = (i == 0 or board[i - 1][j] == '#') and check(i, j, 1, 0)
                down_to_up = (i == m - 1 or board[i + 1][j] == '#') and check(
                    i, j, -1, 0
                )
                if left_to_right or right_to_left or up_to_down or down_to_up:
                    return True
        return False

Continue Practicing

#1958 check if move is legal #2397 maximum rows covered by columns #2017 grid game