Check if Word Can Be Placed In Crossword - Video Solutions
Leetcode:Check if Word Can Be Placed In Crossword
Check if Word Can Be Placed In Crossword - Video Solution
Watch 5 video solutions for Check if Word Can Be Placed In Crossword, a medium level problem involving Array, Matrix, Enumeration. This walkthrough by Coding For Dummies has 1,962 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an m x n matrix board, representing the current state of a crossword puzzle. The crossword contains lowercase English letters (from solved words), ' ' to represent any empty cells, and '#' to represent any blocked cells.
A word can be placed horizontally (left to right or right to left) or vertically (top to bottom or bottom to top) in the board if:
- It does not occupy a cell containing the character
'#'. - The cell each letter is placed in must either be
' '(empty) or match the letter already on theboard. - There must not be any empty cells
' 'or other lowercase letters directly left or right of the word if the word was placed horizontally. - There must not be any empty cells
' 'or other lowercase letters directly above or below the word if the word was placed vertically.
Given a string word, return true if word can be placed in board, or false otherwise.
Example 1:
Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc" Output: true Explanation: The word "abc" can be placed as shown above (top to bottom).
Example 2:
Input: board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac" Output: false Explanation: It is impossible to place the word because there will always be a space/letter above or below it.
Example 3:
Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "ca" Output: true Explanation: The word "ca" can be placed as shown above (right to left).
Constraints:
m == board.lengthn == board[i].length1 <= m * n <= 2 * 105board[i][j]will be' ','#', or a lowercase English letter.1 <= word.length <= max(m, n)wordwill contain only lowercase English letters.
Approach Overview
Problem Overview: You are given a crossword board containing letters, blank cells, and blocked cells (#). The task is to check whether a given word can be placed horizontally or vertically so that it fits exactly between blocks while matching existing letters.
Approach 1: Greedy Check for Each Row and Column (O(m * n * k) time, O(1) space)
Scan every row and column and treat each segment between # characters as a potential placement slot. If the segment length equals the word length k, try matching the word character by character. A match is valid when the board cell is either blank or already contains the same character. Perform this check for both forward and reversed versions of the word to support placements in either direction. This method relies on straightforward enumeration of segments in the array and matrix, making it easy to implement but slightly redundant because each slot is checked twice.
Approach 2: Advanced Optimized Inline Check (O(m * n) time, O(1) space)
Instead of extracting segments first, iterate through each cell and detect valid starting points of a word. A cell is a valid start if it is not a block and the previous cell in that direction is either out of bounds or #. From this start position, verify whether the next k cells can host the word while ensuring the cell after the segment is a boundary or block. During the scan, check both forward and reverse character alignment inline without building temporary strings. This removes redundant segment scans and keeps the traversal strictly linear across the grid. The approach uses direct index checks on the matrix while enumerating candidates using enumeration.
Recommended for interviews: The greedy row and column scan clearly demonstrates the constraints of the crossword slots and is easy to reason about, so it works well as an initial explanation. Interviewers usually expect the optimized inline scan afterward because it eliminates unnecessary segment creation and achieves a clean O(m * n) traversal while maintaining constant extra space.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Check for Each Row and Column | O(m * n * k) | O(1) | Clear and straightforward implementation when explaining the slot matching idea |
| Advanced Optimized Inline Check | O(m * n) | O(1) | Preferred interview solution when you want a single linear traversal of the grid |