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:
'#'.' ' (empty) or match the letter already on the board.' ' or other lowercase letters directly left or right of the word if the word was placed horizontally.' ' 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)word will contain only lowercase English letters.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.
This approach involves scanning each row and each column of the board to check if the word can fit. We examine potential start positions and ensure constraints are satisfied, such as boundary conditions and adjacent cell checks.
The C solution involves two main functions: checkRow checks if a word can be placed in a specified row, and checkCol does the same for a specified column. Each function checks both directions (left-to-right/right-to-left or top-to-bottom/bottom-to-top). Boundary conditions and matching constraints are validated for a successful placement.
Time Complexity: O(m * n * max(m, n)), where m is the number of rows and n is the number of columns in the board.
Space Complexity: O(1) since we are using a constant amount of extra space.
This method involves an inline checking process where we simultaneously explore the suitability of a position for rows and columns while moving through the board, optimizing early exits and reducing redundant checks.
C code optimizes word checks by combining inline checks for word placement in rows and columns, leveraging bridging checks based on initial cell values to minimize evaluations.
Time Complexity: O(m * n * max(m, n)), where m is the number of rows and n is the number of columns in the board.
Space Complexity: O(1).
We can enumerate each position (i, j) in the matrix, and judge whether we can place the word word from left to right or from right to left, or from top to bottom or from bottom to top, starting from this position.
The following conditions must be met for this position to be used as a starting point:
word is to be placed from left to right, then this position must be the left boundary, or the cell board[i][j - 1] to the left of this position is '#'.word is to be placed from right to left, then this position must be the right boundary, or the cell board[i][j + 1] to the right of this position is '#'.word is to be placed from top to bottom, then this position must be the upper boundary, or the cell board[i - 1][j] above this position is '#'.word is to be placed from bottom to top, then this position must be the lower boundary, or the cell board[i + 1][j] below this position is '#'.Under the above conditions, we can start from this position and judge whether the word word can be placed. We design a function check(i, j, a, b), which represents whether it is legal to place the word word from the position (i, j) in the direction (a, b). If it is legal, return true, otherwise return false.
The implementation of the function check(i, j, a, b) is as follows:
We first get the other boundary position (x, y) in the current direction, i.e., (x, y) = (i + a times k, j + b times k), where k is the length of the word word. If (x, y) is in the matrix and the cell at (x, y) is not '#', it means that the other boundary position in the current direction is not '#', so the word word cannot be placed, and false is returned.
Otherwise, we start from the position (i, j) and traverse the word word in the direction (a, b). If we encounter a cell board[i][j] that is not a space or not the current character of the word word, it means that the word word cannot be placed, and false is returned. If the word word is traversed, it means that the word word can be placed, and true is returned.
The time complexity is O(m times n), and the space complexity is O(1). Here, m and n are the number of rows and columns in the matrix, respectively.
| Approach | Complexity |
|---|---|
| Greedy Check for Each Row and Column | Time Complexity: O(m * n * max(m, n)), where m is the number of rows and n is the number of columns in the board. |
| Advanced Optimized Inline Check | Time Complexity: O(m * n * max(m, n)), where m is the number of rows and n is the number of columns in the board. |
| Enumeration | — |
| 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 |
Leetcode:Check if Word Can Be Placed In Crossword • Coding For Dummies • 1,941 views views
Watch 4 more video solutions →Practice Check if Word Can Be Placed In Crossword with our built-in code editor and test cases.
Practice on FleetCode