Check if Word Can Be Placed In Crossword

Check if Word Can Be Placed In Crossword

What is this problem about?

You are given an $m imes n$ grid representing a crossword board and a target string word. The grid contains empty spaces (' '), walls ('#'), and pre-filled letters. You need to determine if the word can be placed in any horizontal or vertical slot that is bounded by walls or the grid edges. The word must fit exactly—it cannot be shorter than the slot.

Why is this asked in interviews?

Google uses this "Medium" problem to test your Matrix traversal and Enumeration skills. It’s a test of whether you can handle multidimensional constraints and multiple directions (Forward, Backward, Horizontal, Vertical). It evaluations your attention to detail regarding slot boundaries and matching rules.

Algorithmic pattern used

The pattern is Enumeration and Linear Scan. You iterate through every possible starting position and direction. However, a more efficient way is to find all "slots" (sequences of non-wall cells). For each slot, you check if the target word (or its reverse) matches the characters in that slot and if the slot length is exactly equal to the word length.

Example explanation

Grid: ' ' ' ' '#' 'a' ' ' '#' Target word: "ca"

1. Row 0 has a slot of length 4. "ca" is too short.
2. Row 1 has a slot of length 2. The first letter is 'a'. "ca" does not match.
3. Column 0 has a slot of length 2. The first letter is ' ', second is 'a'. "ca" fits if you put 'c' in the empty space! Result: True.

Common mistakes candidates make

A common error is forgetting to check the word in reverse order (e.g., "ca" can be placed as "ac" in a slot). Another is allowing a word to be placed in a slot that is longer than the word itself. Candidates also often struggle with the logic for splitting rows and columns into slots efficiently.

Interview preparation tip

For matrix problems with many conditions, try to isolate the "candidate" regions first. In this case, finding all the "slots" (using a wall as a delimiter) simplifies the problem into a simple string matching task.