Abstract / Summary

Check if a word fits in a grid at a given position considering existing letters and word boundaries

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 50% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Enumeration
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The placeWordInCrossword method determines whether a given word can be placed on a crossword board either horizontally or vertically. The board consists of empty cells represented by a space ' ' and blocked cells represented by '#'. The word may be placed in either forward or reverse order, but it must exactly fill a contiguous sequence of non-blocked cells without leaving any gaps.

Extraction of Horizontal and Vertical Patterns

The algorithm first records every maximal stretch of cells that are not blocked. It does this separately for rows and columns, appending each stretch to a single list called patterns.

width  = len(board[0])
height = len(board)

patterns = [ "" ]
for y in range(height):
    patterns.append("")
    for x in range(width):
        if board[y][x] == "#":
            patterns.append("")
        else:
            patterns[-1] += board[y][x]

The outer loop iterates over each row index y. For each row a new empty string is added to patterns. As the inner loop walks across the columns, a blocked cell triggers the start of a new pattern, while any other character (including a space) is concatenated to the current pattern.

The same logic is applied to columns, building vertical patterns in a similar fashion.

for x in range(width):
    patterns.append("")
    for y in range(height):
        if board[y][x] == "#":
            patterns.append("")
        else:
            patterns[-1] += board[y][x]

By the end of these two loops, patterns contains every horizontal and vertical segment of the board that could potentially host the word.

Normalization and Matching

To compare the collected patterns with the target word, the method first removes duplicate entries by converting the list to a set. It then iterates over each unique pattern, discarding any whose length differs from the word’s length, because such a pattern could never accommodate the word.

for p in set(patterns):
    if len(p) != len(word):
        continue

Each remaining pattern may contain spaces that represent empty cells. The code replaces spaces with the regex wildcard . so that a regular-expression search can treat any empty cell as a match for any character of the word.

p = p.replace(" ", ".")

A forward search checks whether the word fits the pattern as-is. A second search checks the reversed word, allowing placement in the opposite direction. If either search succeeds, the function returns True.

if re.search(p, word):
    return True
if re.search(p, word[::-1]):
    return True

If no pattern matches, the method finally returns False.

Edge Cases Handled

The implementation gracefully handles boards that contain only blocked cells, because the pattern extraction loops will generate only empty strings, which are filtered out by the length check. Boards with varying numbers of rows and columns are supported, as the dimensions are derived directly from the input list.

Segments that consist solely of spaces are treated as valid placement zones; the space-to-dot conversion turns the entire segment into a series of wildcards, allowing any word of matching length to occupy it.

When a segment contains a mixture of spaces and letters, the regex engine ensures that the letters in the segment must align exactly with the corresponding letters of the word, while spaces remain flexible.

The reverse-order check guarantees that words can be placed backward without requiring a separate extraction of reversed patterns.

Performance Optimizations

The use of a set to eliminate duplicate patterns reduces the number of regular-expression searches, especially on boards where many rows or columns share identical stretches.

The early continue for length mismatches prevents unnecessary regex compilation and matching for patterns that could never succeed, saving computational effort.

By building both horizontal and vertical patterns in a single pass over the board, the algorithm avoids the overhead of constructing separate data structures for each orientation.

Overall, the method leverages Python’s built-in string concatenation and set operations to keep the core loops concise and efficient while still covering all necessary placement scenarios.

Think of the board like a giant grid of boxes on a large sheet of paper. Some boxes have letters inside them already, while others have dark blocks that act like walls. This code is trying to find a special spot where a hidden word can fit perfectly.

First, the code looks at every single row and every single column to find empty spaces tucked between the walls. It treats these lines of empty spaces like little treasure paths. It ignores the walls and just gathers all the available spots in a row or column into a list.

After collecting all those paths, the code checks each one to see if the length matches the number of letters in the mystery word. If the length is right, it looks at the spaces inside the path. Some spaces might be empty, while others might already have a letter waiting there. If the letters on the board match the letters in the word, or if the spaces are empty and ready to be filled, the word fits.

The code also checks the word backward just in case it needs to be written from bottom to top or from right to left. By looking at all the paths this way, it figures out if the puzzle can be solved by placing the word somewhere on the grid.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java			TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality