Practice/Google/2018. Check if Word Can Be Placed In Crossword

2018. Check if Word Can Be Placed In Crossword

CodingOptional

Problem

You are given a crossword puzzle grid represented as a 2D array of characters and a word. The grid contains:

• ' ' (space) representing empty cells
• '#' representing blocked cells (walls)
• Lowercase letters representing cells with pre-filled characters

Determine whether the given word can be placed in the crossword grid either horizontally (left-to-right or right-to-left) or vertically (top-to-bottom or bottom-to-top).

A word can be placed in a slot if:

1. The slot has exactly the same length as the word
2. The slot is bounded by blocked cells ('#') or grid boundaries on both ends
3. Each position in the slot is either empty (' ') or contains the same letter as the corresponding position in the word
4. The slot must be exactly the word's length (no extra spaces)

Requirements

1. Check both horizontal and vertical orientations
2. Check both forward and backward directions for each orientation
3. A valid placement must match the exact length of the word
4. Pre-filled letters in the grid must match corresponding positions in the word
5. Return true if the word can be placed in at least one valid slot, false otherwise

Constraints

• 1 ≤ m, n ≤ 100 (where m × n is the grid size)
• 1 ≤ word.length ≤ max(m, n)
• The word contains only lowercase English letters
• Grid cells contain only ' ', '#', or lowercase English letters
• Time complexity should be O(m × n × word.length)
• Space complexity should be O(1) excluding the input

Examples

Example 1:

` Input: grid = [ ['#', ' ', ' ', '#'], ['#', ' ', '#', '#'], ['#', ' ', ' ', ' '] ] word = "cat"

Output: true

Explanation: The word "cat" can be placed horizontally in the third row starting at column index 1. The slot has length 3, bounded by '#' on the left and the grid boundary on the right. `

Example 2:

` Input: grid = [ ['#', ' ', '#'], ['#', ' ', '#'], ['#', ' ', '#'] ] word = "dog"

Output: true

Explanation: The word "dog" can be placed vertically in column index 1. The slot spans all three rows and is bounded by '#' on both sides. `

Example 3:

` Input: grid = [ [' ', ' ', ' ', ' '], ['#', 'x', 'y', 'z'] ] word = "code"

Output: false

Explanation: No valid slot of length 4 exists where "code" matches the pattern. The second row has pre-filled letters that don't match "code". `