LeetCode 2018 - Check if Word Can Be Placed In Crossword

LeetCode Problem 2018

Difficulty: 🟡 Medium
Topics: Array, Matrix, Enumeration

Solution

Problem Understanding

This problem asks us to determine whether a given word can be legally placed into a crossword board while respecting crossword placement rules.

The input consists of a 2D matrix called board, where each cell can contain one of three possible values:

'#', representing a blocked cell that cannot be used.
' ', representing an empty cell that can accept any character.
A lowercase English letter, representing a prefilled letter that must match the corresponding letter of the word.

We are also given a string word, and the task is to return true if the word can be placed somewhere in the crossword, otherwise return false.

The word may be placed in four directions:

Left to right
Right to left
Top to bottom
Bottom to top

However, placement is only valid if all crossword constraints are satisfied.

First, the word cannot overlap any '#' cells. Second, every board cell occupied by the word must either already contain the matching letter or be empty (' '). Third, the word must fit exactly into an available segment. This means the word cannot be part of a larger open space. For horizontal placement, the cells immediately before and after the word must either be outside the board or blocked by '#'. Similarly, for vertical placement, the cells directly above and below must be blocked or out of bounds.

The constraints are important here. Since m * n ≤ 2 * 10^5, the board can become quite large. This tells us that an inefficient brute-force search that repeatedly scans the board for every possible placement could become too slow. We need a solution that runs approximately in linear time relative to the board size.

Several edge cases can easily trip up a naive implementation. A word may only fit in reverse order, meaning we must consider both forward and backward directions. Existing letters on the board might partially match the word and partially block it. A segment may have the correct length but fail because adjacent cells are not blocked. There are also cases where a word appears to fit horizontally but only vertically works, or vice versa.

One important guarantee is that the word length never exceeds max(m, n), meaning it can theoretically fit within at least one row or column.

Approaches

Brute Force Approach

A brute-force solution would try placing the word starting from every cell in all four directions. For each starting point, we would check whether:

The word stays within bounds.
No '#' cells are encountered.
Existing letters match.
The surrounding boundary conditions are valid.

This approach is correct because it explicitly checks every possible legal placement.

However, it is inefficient. Suppose the board has m × n cells and the word length is k. For every cell, we attempt up to four directions, and each validation costs O(k). This results in a time complexity of O(m × n × k).

Although this may still pass in practice for some inputs, it performs unnecessary repeated work because many placements immediately fail due to segment boundaries.

Optimal Approach

The key insight is that valid placements must occur inside contiguous segments separated by '#'.

Instead of testing every starting cell in every direction, we can scan rows and columns and only consider maximal open segments. A valid placement must exactly occupy a segment whose length equals the word length.

For example, consider a row:

# a _ c #

The open segment is "a c" between two '#' characters. If its length matches the word length, we only need to check whether the word matches this segment, either forward or backward.

This observation dramatically simplifies the problem. We process each row and column once, extract segments between '#', and validate only relevant segments.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n × k)	O(1)	Tries every starting cell and direction
Optimal	O(m × n)	O(1)	Scans segments once and validates exact matches

Algorithm Walkthrough

Optimal Algorithm

Define a helper function that checks whether a segment can match the word.

The helper receives a sequence of characters and determines whether the word can fit exactly. The segment length must equal the word length. Then, for every position, the board character must either be ' ' or match the corresponding word character. 2. Also check the reversed word.

Since the word can be placed in both directions, we test both word and word[::-1]. 3. Scan every row.

For each row, split it into contiguous segments separated by '#'. Each segment represents a maximal open space where a word could potentially fit. 4. Validate row segments.

If a segment length equals the word length, test whether it matches either the forward or reversed word. 5. Scan every column.

Repeat the same process vertically. Instead of rows, construct segments column by column. 6. Return early if a valid placement is found.

The moment we discover one legal placement, we return True. 7. If no segment works, return False.

Why it works

The algorithm works because every valid word placement must occupy an uninterrupted segment of non-'#' cells. By scanning only these maximal segments, we guarantee that boundary conditions are automatically satisfied. Since we test both forward and reversed directions and verify every character compatibility rule, every legal placement is checked exactly once.

Python Solution

from typing import List

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        rows = len(board)
        cols = len(board[0])
        reversed_word = word[::-1]

        def matches(segment: List[str], candidate: str) -> bool:
            if len(segment) != len(candidate):
                return False

            for board_char, word_char in zip(segment, candidate):
                if board_char != ' ' and board_char != word_char:
                    return False

            return True

        def check_line(line: List[str]) -> bool:
            start = 0
            length = len(line)

            while start < length:
                while start < length and line[start] == '#':
                    start += 1

                end = start
                while end < length and line[end] != '#':
                    end += 1

                segment = line[start:end]

                if (
                    matches(segment, word)
                    or matches(segment, reversed_word)
                ):
                    return True

                start = end

            return False

        for row in board:
            if check_line(row):
                return True

        for col in range(cols):
            column = [board[row][col] for row in range(rows)]

            if check_line(column):
                return True

        return False

The implementation is organized into two helper functions.

The matches() function checks whether a segment can accommodate a candidate word. It first verifies equal length, since crossword rules require exact fitting. Then it compares characters one by one. A board character is valid if it is empty (' ') or already equals the required letter.

The check_line() function processes either a row or a column. It scans contiguous regions between '#' characters and extracts segments. Each segment is tested against both the original word and its reverse.

The main function first checks every row. If no valid horizontal placement exists, it constructs each column and performs the same logic vertically. The search terminates immediately when a valid placement is found.

Go Solution

func placeWordInCrossword(board [][]byte, word string) bool {
	rows := len(board)
	cols := len(board[0])
	reversedWord := reverse(word)

	matches := func(segment []byte, candidate string) bool {
		if len(segment) != len(candidate) {
			return false
		}

		for i := 0; i < len(candidate); i++ {
			if segment[i] != ' ' && segment[i] != candidate[i] {
				return false
			}
		}

		return true
	}

	checkLine := func(line []byte) bool {
		start := 0
		n := len(line)

		for start < n {
			for start < n && line[start] == '#' {
				start++
			}

			end := start
			for end < n && line[end] != '#' {
				end++
			}

			segment := line[start:end]

			if matches(segment, word) || matches(segment, reversedWord) {
				return true
			}

			start = end
		}

		return false
	}

	for _, row := range board {
		if checkLine(row) {
			return true
		}
	}

	for col := 0; col < cols; col++ {
		column := make([]byte, rows)

		for row := 0; row < rows; row++ {
			column[row] = board[row][col]
		}

		if checkLine(column) {
			return true
		}
	}

	return false
}

func reverse(s string) string {
	bytes := []byte(s)

	left, right := 0, len(bytes)-1
	for left < right {
		bytes[left], bytes[right] = bytes[right], bytes[left]
		left++
		right--
	}

	return string(bytes)
}

The Go implementation follows the same algorithmic structure as the Python version. Since Go strings are immutable, a helper function is used to reverse the word efficiently by converting it into a byte slice.

Columns are explicitly constructed using a temporary []byte slice because Go does not provide convenient column access for a 2D slice. Otherwise, the logic remains identical.

There are no integer overflow concerns here because the constraints are well within Go's standard integer range.

Worked Examples

Example 1

board =
[
    ['#', ' ', '#'],
    [' ', ' ', '#'],
    ['#', 'c', ' ']
]

word = "abc"

We first scan rows.

Row	Segment	Length Match?	Valid?
`# #`	`" "`	No	Skip
`#`	`" "`	No	Skip
`#c`	`"c "`	No	Skip

No horizontal placement works.

Now scan columns.

Column 1:

[' ', ' ', 'c']

Segment length equals 3.

Check against "abc":

Position	Board	Word	Valid
0	`' '`	`'a'`	Yes
1	`' '`	`'b'`	Yes
2	`'c'`	`'c'`	Yes

All positions match, so return True.

Example 2

board =
[
    [' ', '#', 'a'],
    [' ', '#', 'c'],
    [' ', '#', 'a']
]

word = "ac"

Check first column:

[' ', ' ', ' ']

Length is 3, not 2.

Third column:

['a', 'c', 'a']

Length is 3, not 2.

No segment has exact length 2, meaning the word cannot fit without violating boundary rules.

Return False.

Example 3

board =
[
    ['#', ' ', '#'],
    [' ', ' ', '#'],
    ['#', ' ', 'c']
]

word = "ca"

Row 3 segment:

[' ', 'c']

Try "ca":

' ' matches 'c'
'c' does not match 'a'

Fails.

Try reversed "ac":

' ' matches 'a'
'c' matches 'c'

Success.

Return True.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every cell is processed a constant number of times
Space	O(1)	Only a few variables are used, excluding temporary column construction

The algorithm scans every row and column exactly once. Since each cell participates in at most one row scan and one column scan, the total work is linear in the board size. Although a temporary column slice is created in Go, and Python constructs slices for segments, the extra memory remains proportional to a single row or column rather than the whole board, which is effectively constant relative to input size.

Test Cases

solution = Solution()

# Example 1
assert solution.placeWordInCrossword(
    [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]],
    "abc"
) is True  # vertical placement

# Example 2
assert solution.placeWordInCrossword(
    [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]],
    "ac"
) is False  # boundary violation

# Example 3
assert solution.placeWordInCrossword(
    [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]],
    "ca"
) is True  # reverse horizontal placement

# Single cell match
assert solution.placeWordInCrossword(
    [["a"]],
    "a"
) is True  # exact character match

# Single empty cell
assert solution.placeWordInCrossword(
    [[" "]],
    "z"
) is True  # empty cell accepts any letter

# Single blocked cell
assert solution.placeWordInCrossword(
    [["#"]],
    "a"
) is False  # blocked position

# Exact fit required
assert solution.placeWordInCrossword(
    [[" ", " ", " "]],
    "ab"
) is False  # segment too large

# Reverse vertical placement
assert solution.placeWordInCrossword(
    [["c"], [" "]],
    "ac"
) is True  # bottom-to-top placement

# Prefilled mismatch
assert solution.placeWordInCrossword(
    [["a", "b", "c"]],
    "abd"
) is False  # conflicting character

# Multiple segments
assert solution.placeWordInCrossword(
    [["#", " ", "#", "a", " "]],
    "ab"
) is True  # valid second segment

Test	Why
Example 1	Validates vertical placement
Example 2	Validates strict boundary rules
Example 3	Ensures reverse placement works
Single cell match	Smallest valid board
Single empty cell	Empty cells accept any letter
Single blocked cell	Blocked cell cannot be used
Exact fit required	Prevents partial segment usage
Reverse vertical placement	Verifies bottom-to-top logic
Prefilled mismatch	Detects conflicting characters
Multiple segments	Ensures scanning continues correctly

Edge Cases

Word Fits Only in Reverse Direction

A common bug is forgetting that words can be placed right to left or bottom to top. For example, a segment might fail for "abc" but succeed for "cba". The implementation avoids this issue by always checking both word and word[::-1].

Segment Is Larger Than the Word

A naive implementation may accidentally allow placing a word inside a larger open space. For example:

[ ' ', ' ', ' ' ]

with word "ab".

This placement is invalid because there would still be adjacent open cells. Our algorithm prevents this by requiring the segment length to exactly equal the word length.

Existing Letters Conflict

The board may already contain letters that partially overlap the word. For example:

[a, b, c]

with word "abd".

Even though the first two letters match, the final position conflicts. The matches() function explicitly verifies every character, rejecting placements where a prefilled letter differs from the required letter.