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

Leetcode 2018. Check if Word Can Be Placed In Crossword

CodingOptional

Problem

You are given a rectangular grid representing a puzzle board and a target word. The grid contains three types of cells:

• Block cells (represented by '#'): These are solid barriers where no letters can be placed
• Blank cells (represented by ' '): Empty spaces where any letter can be placed
• Letter cells (represented by lowercase letters): Pre-filled cells containing specific letters

Your task is to determine whether the given word can be validly placed in the grid either horizontally or vertically, in either forward or backward direction.

A valid placement means:

• The word occupies a contiguous sequence of non-block cells
• Each position either contains a blank space OR matches the corresponding letter in the word
• The word's starting position is at a grid boundary OR immediately preceded by a block cell
• The word's ending position is at a grid boundary OR immediately followed by a block cell
• The word exactly fills the slot (no extra spaces beyond the word in that direction)

Return true if at least one valid placement exists, otherwise return false.

Requirements

1. Check all possible horizontal positions (left-to-right and right-to-left)
2. Check all possible vertical positions (top-to-bottom and bottom-to-top)
3. Ensure each placement is properly bounded (starts and ends at edges or blocks)
4. Verify that the word length exactly matches the slot length
5. Confirm that pre-existing letters either match the word or the cell is blank

Constraints

• m == board.length (number of rows)
• n == board[i].length (number of columns)
• 1 <= m * n <= 2 * 10^5
• 1 <= word.length <= max(m, n)
• board[i][j] is either '#', ' ', or a lowercase English letter
• word consists only of lowercase English letters

Examples

Example 1:

Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "abc" Output: true Explanation: The word can be placed vertically in column 1 (middle column) reading downward: position [0][1]='a', [1][1]='b', [2][1]='c'.

Example 2:

Input: board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "aca" Output: true Explanation: The word matches the existing letters in column 2 reading from top to bottom.

Example 3:

Input: board = [["#", "#", "#"], ["#", "#", "#"], ["#", "#", "#"]], word = "test" Output: false Explanation: All cells are blocked, so there's no place to put any word.

Example 4:

Input: board = [[" ", " ", " ", " "]], word = "abcd" Output: true Explanation: The word fits perfectly in the single row horizontally.