2018. Check if Word Can Be Placed In Crossword

MediumArrayEnumerationMatrix

Problem Description

You have an m x n matrix board representing a crossword puzzle with the following elements:

Lowercase English letters (from already solved words)
' ' (spaces) representing empty cells
'#' representing blocked cells

You need to determine if a given word can be placed in the crossword puzzle either horizontally or vertically in any of the four directions:

Horizontally: left-to-right or right-to-left
Vertically: top-to-bottom or bottom-to-top

The placement rules are:

The word cannot occupy any cell containing '#'
Each letter of the word must either:
- Be placed in an empty cell ' ', OR
- Match the existing letter already in that cell
For horizontal placement: There cannot be any empty cells ' ' or other lowercase letters directly to the left or right of the word
For vertical placement: There cannot be any empty cells ' ' or other lowercase letters directly above or below the word

In other words, the word must fit exactly in a slot bounded by either the matrix edges or '#' characters, and any existing letters in that slot must match the corresponding letters in the word.

Return true if the word can be placed anywhere in the board following these rules, otherwise return false.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that in a crossword puzzle, words must fit into specific "slots" that are bounded by either the edges of the board or blocked cells ('#'). We can't place a word in the middle of an existing word or have it extend beyond its designated slot.

Think about how you would manually check if a word fits in a crossword: you'd look for potential starting positions and try placing the word in different directions from each position. A valid starting position must be at the beginning of a slot - either at the board's edge or right after a '#' character.

For each position (i, j) in the matrix, we can try placing the word in four possible directions:

Left to right (direction vector: (0, 1))
Right to left (direction vector: (0, -1))
Top to bottom (direction vector: (1, 0))
Bottom to top (direction vector: (-1, 0))

But not every position can be a valid starting point. For example, if we want to place a word from left to right starting at (i, j), then either j must be 0 (left edge of the board) or board[i][j-1] must be '#' (blocked cell to the left). This ensures we're at the beginning of a horizontal slot.

Once we have a valid starting position and direction, we need to verify two things:

The word fits within the slot (doesn't extend beyond the ending boundary)
Each character either goes into an empty space or matches an existing letter

The ending boundary check is crucial - after placing the word, the next cell in that direction must either be out of bounds or contain '#'. This ensures the word doesn't merge with adjacent words or leave empty spaces within a slot.

By systematically checking all possible starting positions and directions, we can determine if there's at least one valid placement for the word.

Solution Approach

The solution uses an enumeration approach where we check every possible position and direction for placing the word.

Main Algorithm Structure:

We iterate through each cell (i, j) in the matrix and check if the word can be placed starting from this position in any of the four directions. The main loop structure is:

for i in range(m):
    for j in range(n):
        # Check all 4 directions from position (i, j)

Helper Function - check(i, j, a, b):

This function validates whether we can place the word starting from position (i, j) in the direction (a, b). The direction vectors are:

(0, 1) for left-to-right
(0, -1) for right-to-left
(1, 0) for top-to-bottom
(-1, 0) for bottom-to-top

The function performs two key validations:

End boundary check: Calculate the position after the word ends: (x, y) = (i + a * k, j + b * k) where k is the word length. If this position is within bounds and not a '#', the word would improperly extend into another slot, so we return false.
Character-by-character validation: Traverse each character of the word in the given direction. For each character c:
- Check if we're still within matrix bounds
- Verify that the current cell is either empty (' ') or contains the matching character c
- Move to the next position: (i, j) = (i + a, j + b)

Starting Position Validation:

Before calling check, we verify that the position is a valid starting point for each direction:

Left-to-right: Must be at left edge (j == 0) or have '#' to the left (board[i][j-1] == '#')
Right-to-left: Must be at right edge (j == n-1) or have '#' to the right (board[i][j+1] == '#')
Top-to-bottom: Must be at top edge (i == 0) or have '#' above (board[i-1][j] == '#')
Bottom-to-top: Must be at bottom edge (i == m-1) or have '#' below (board[i+1][j] == '#')

Final Decision:

If any of the four directional checks from any position returns true, we immediately return true. If we've checked all positions and directions without finding a valid placement, we return false.

The time complexity is O(m * n * k) where m and n are the matrix dimensions and k is the word length, as we potentially check each position and traverse the word for validation. The space complexity is O(1) as we only use a constant amount of extra space.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example:

board = [['#', ' ', '#'],
         [' ', ' ', '#'],
         ['#', 'c', ' ']]
word = "abc"

We need to check if "abc" can be placed anywhere on this 3×3 board.

Step 1: Check position (0,0)

Cell contains '#', so we skip all directions from this position.

Step 2: Check position (0,1)

Cell contains ' ' (empty)
Left-to-right: Check if (0,0) is '#' → Yes! Valid starting position.
- End boundary: (0, 1+3) = (0,4) is out of bounds → Good!
- Character validation:
  - 'a' at (0,1): ' ' is empty → OK
  - 'b' at (0,2): '#' is blocked → FAIL
Right-to-left: Check if (0,2) is '#' → Yes! Valid starting position.
- End boundary: (0, 1-3) = (0,-2) is out of bounds → Good!
- Character validation:
  - 'a' at (0,1): ' ' is empty → OK
  - 'b' at (0,0): '#' is blocked → FAIL
Top-to-bottom: At top edge (i=0) → Valid starting position.
- End boundary: (0+3, 1) = (3,1) is out of bounds → Good!
- Character validation:
  - 'a' at (0,1): ' ' is empty → OK
  - 'b' at (1,1): ' ' is empty → OK
  - 'c' at (2,1): 'c' matches → OK
- SUCCESS! Word can be placed vertically from (0,1) to (2,1)

Since we found a valid placement, we return true.

The word "abc" fits perfectly in the vertical slot from position (0,1) downward:

board after placement:
[['#', 'a', '#'],
 [' ', 'b', '#'],
 ['#', 'c', ' ']]

Note how:

The slot is bounded by the top edge above and '#' below at position (3,1)
The existing 'c' at position (2,1) matches the third letter of our word
No empty spaces or letters extend beyond the word in the vertical direction

Solution Implementation

1class Solution:
2    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
3        """
4        Check if a word can be placed in a crossword board.
5        The word can be placed horizontally (left-to-right or right-to-left)
6        or vertically (up-to-down or down-to-up).
7        """
8      
9        def can_place_word(start_row: int, start_col: int, row_delta: int, col_delta: int) -> bool:
10            """
11            Check if the word can be placed starting from (start_row, start_col)
12            in the direction specified by (row_delta, col_delta).
13          
14            Args:
15                start_row: Starting row position
16                start_col: Starting column position
17                row_delta: Row increment for each character (-1, 0, or 1)
18                col_delta: Column increment for each character (-1, 0, or 1)
19          
20            Returns:
21                True if word can be placed, False otherwise
22            """
23            # Check if the position after the word would be a boundary (# or edge)
24            end_row = start_row + row_delta * word_length
25            end_col = start_col + col_delta * word_length
26          
27            # Ensure the cell after the word (if exists) is blocked
28            if 0 <= end_row < rows and 0 <= end_col < cols and board[end_row][end_col] != '#':
29                return False
30          
31            # Check each character of the word
32            current_row, current_col = start_row, start_col
33            for char in word:
34                # Check if current position is out of bounds
35                if current_row < 0 or current_row >= rows or current_col < 0 or current_col >= cols:
36                    return False
37              
38                # Check if current cell can accommodate the character
39                # Cell must be either empty (' ') or match the character
40                if board[current_row][current_col] != ' ' and board[current_row][current_col] != char:
41                    return False
42              
43                # Move to next position
44                current_row += row_delta
45                current_col += col_delta
46          
47            return True
48      
49        # Get board dimensions and word length
50        rows, cols = len(board), len(board[0])
51        word_length = len(word)
52      
53        # Try placing the word starting from each cell
54        for row in range(rows):
55            for col in range(cols):
56                # Check horizontal placement (left to right)
57                # Valid if at left edge or previous cell is blocked
58                can_place_left_to_right = (col == 0 or board[row][col - 1] == '#') and can_place_word(row, col, 0, 1)
59              
60                # Check horizontal placement (right to left)
61                # Valid if at right edge or next cell is blocked
62                can_place_right_to_left = (col == cols - 1 or board[row][col + 1] == '#') and can_place_word(row, col, 0, -1)
63              
64                # Check vertical placement (top to bottom)
65                # Valid if at top edge or cell above is blocked
66                can_place_top_to_bottom = (row == 0 or board[row - 1][col] == '#') and can_place_word(row, col, 1, 0)
67              
68                # Check vertical placement (bottom to top)
69                # Valid if at bottom edge or cell below is blocked
70                can_place_bottom_to_top = (row == rows - 1 or board[row + 1][col] == '#') and can_place_word(row, col, -1, 0)
71              
72                # If word can be placed in any direction, return True
73                if can_place_left_to_right or can_place_right_to_left or can_place_top_to_bottom or can_place_bottom_to_top:
74                    return True
75      
76        # Word cannot be placed anywhere
77        return False
78

1class Solution {
2    // Board dimensions
3    private int rows;
4    private int cols;
5  
6    // Input data
7    private char[][] board;
8    private String word;
9    private int wordLength;
10
11    /**
12     * Determines if a word can be placed in the crossword board.
13     * The word can be placed horizontally (left-to-right or right-to-left)
14     * or vertically (top-to-bottom or bottom-to-top).
15     * 
16     * @param board 2D character array representing the crossword
17     * @param word the word to be placed
18     * @return true if the word can be placed, false otherwise
19     */
20    public boolean placeWordInCrossword(char[][] board, String word) {
21        // Initialize instance variables
22        this.rows = board.length;
23        this.cols = board[0].length;
24        this.board = board;
25        this.word = word;
26        this.wordLength = word.length();
27      
28        // Try placing the word starting from each cell
29        for (int row = 0; row < rows; row++) {
30            for (int col = 0; col < cols; col++) {
31                // Check if word can be placed starting at (row, col) in any direction
32              
33                // Left to right: valid if at left boundary or blocked on the left
34                boolean canPlaceLeftToRight = (col == 0 || board[row][col - 1] == '#') 
35                    && canPlaceWord(row, col, 0, 1);
36              
37                // Right to left: valid if at right boundary or blocked on the right
38                boolean canPlaceRightToLeft = (col == cols - 1 || board[row][col + 1] == '#') 
39                    && canPlaceWord(row, col, 0, -1);
40              
41                // Top to bottom: valid if at top boundary or blocked above
42                boolean canPlaceTopToBottom = (row == 0 || board[row - 1][col] == '#') 
43                    && canPlaceWord(row, col, 1, 0);
44              
45                // Bottom to top: valid if at bottom boundary or blocked below
46                boolean canPlaceBottomToTop = (row == rows - 1 || board[row + 1][col] == '#') 
47                    && canPlaceWord(row, col, -1, 0);
48              
49                // If word can be placed in any direction, return true
50                if (canPlaceLeftToRight || canPlaceRightToLeft || 
51                    canPlaceTopToBottom || canPlaceBottomToTop) {
52                    return true;
53                }
54            }
55        }
56      
57        return false;
58    }
59
60    /**
61     * Checks if the word can be placed starting at position (row, col)
62     * in the direction specified by (rowDelta, colDelta).
63     * 
64     * @param row starting row position
65     * @param col starting column position
66     * @param rowDelta row increment for direction (1 for down, -1 for up, 0 for horizontal)
67     * @param colDelta column increment for direction (1 for right, -1 for left, 0 for vertical)
68     * @return true if the word fits in the specified direction, false otherwise
69     */
70    private boolean canPlaceWord(int row, int col, int rowDelta, int colDelta) {
71        // Calculate the end position of the word
72        int endRow = row + rowDelta * wordLength;
73        int endCol = col + colDelta * wordLength;
74      
75        // Check if there's a blocking cell immediately after the word ends
76        // Word should either end at boundary or be followed by a '#'
77        if (endRow >= 0 && endRow < rows && endCol >= 0 && endCol < cols 
78            && board[endRow][endCol] != '#') {
79            return false;
80        }
81      
82        // Check each character position where the word would be placed
83        for (int charIndex = 0; charIndex < wordLength; charIndex++) {
84            // Check if current position is within bounds
85            if (row < 0 || row >= rows || col < 0 || col >= cols) {
86                return false;
87            }
88          
89            // Check if current cell can accommodate the character
90            // Cell must be either empty (' ') or already contain the matching character
91            if (board[row][col] != ' ' && board[row][col] != word.charAt(charIndex)) {
92                return false;
93            }
94          
95            // Move to next position in the specified direction
96            row += rowDelta;
97            col += colDelta;
98        }
99      
100        return true;
101    }
102}
103

1class Solution {
2public:
3    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
4        int rows = board.size();
5        int cols = board[0].size();
6        int wordLength = word.size();
7      
8        // Lambda function to check if word can be placed starting from (row, col) in direction (deltaRow, deltaCol)
9        auto canPlaceWord = [&](int row, int col, int deltaRow, int deltaCol) {
10            // Check if the position after the word ends is blocked or out of bounds
11            int endRow = row + deltaRow * wordLength;
12            int endCol = col + deltaCol * wordLength;
13            if (endRow >= 0 && endRow < rows && endCol >= 0 && endCol < cols && board[endRow][endCol] != '#') {
14                return false;  // The slot doesn't end properly (should be blocked or boundary)
15            }
16          
17            // Check each character of the word
18            for (char& ch : word) {
19                // Check if current position is out of bounds
20                if (row < 0 || row >= rows || col < 0 || col >= cols) {
21                    return false;
22                }
23              
24                // Check if current cell is compatible with the character
25                // Cell must be either empty (' ') or contain the same character
26                if (board[row][col] != ' ' && board[row][col] != ch) {
27                    return false;
28                }
29              
30                // Move to next position in the direction
31                row += deltaRow;
32                col += deltaCol;
33            }
34          
35            return true;
36        };
37      
38        // Try placing the word from every valid starting position
39        for (int i = 0; i < rows; ++i) {
40            for (int j = 0; j < cols; ++j) {
41                // Check horizontal placement (left to right)
42                // Valid start: left boundary or blocked cell on the left
43                bool canPlaceLeftToRight = (j == 0 || board[i][j - 1] == '#') && canPlaceWord(i, j, 0, 1);
44              
45                // Check horizontal placement (right to left)
46                // Valid start: right boundary or blocked cell on the right
47                bool canPlaceRightToLeft = (j == cols - 1 || board[i][j + 1] == '#') && canPlaceWord(i, j, 0, -1);
48              
49                // Check vertical placement (top to bottom)
50                // Valid start: top boundary or blocked cell above
51                bool canPlaceTopToBottom = (i == 0 || board[i - 1][j] == '#') && canPlaceWord(i, j, 1, 0);
52              
53                // Check vertical placement (bottom to top)
54                // Valid start: bottom boundary or blocked cell below
55                bool canPlaceBottomToTop = (i == rows - 1 || board[i + 1][j] == '#') && canPlaceWord(i, j, -1, 0);
56              
57                // If word can be placed in any direction, return true
58                if (canPlaceLeftToRight || canPlaceRightToLeft || canPlaceTopToBottom || canPlaceBottomToTop) {
59                    return true;
60                }
61            }
62        }
63      
64        return false;  // Word cannot be placed anywhere
65    }
66};
67

1function placeWordInCrossword(board: string[][], word: string): boolean {
2    const rows = board.length;
3    const cols = board[0].length;
4    const wordLength = word.length;
5  
6    /**
7     * Check if word can be placed starting from (row, col) in direction (deltaRow, deltaCol)
8     * @param row - Starting row position
9     * @param col - Starting column position
10     * @param deltaRow - Row direction increment (-1, 0, or 1)
11     * @param deltaCol - Column direction increment (-1, 0, or 1)
12     * @returns true if word can be placed, false otherwise
13     */
14    const canPlaceWord = (row: number, col: number, deltaRow: number, deltaCol: number): boolean => {
15        // Check if the position after the word ends is blocked or out of bounds
16        const endRow = row + deltaRow * wordLength;
17        const endCol = col + deltaCol * wordLength;
18      
19        // The slot should end with a boundary or a blocked cell '#'
20        if (endRow >= 0 && endRow < rows && endCol >= 0 && endCol < cols && board[endRow][endCol] !== '#') {
21            return false;
22        }
23      
24        // Check each character of the word
25        for (const ch of word) {
26            // Check if current position is out of bounds
27            if (row < 0 || row >= rows || col < 0 || col >= cols) {
28                return false;
29            }
30          
31            // Check if current cell is compatible with the character
32            // Cell must be either empty (' ') or contain the same character
33            if (board[row][col] !== ' ' && board[row][col] !== ch) {
34                return false;
35            }
36          
37            // Move to next position in the direction
38            row += deltaRow;
39            col += deltaCol;
40        }
41      
42        return true;
43    };
44  
45    // Try placing the word from every valid starting position
46    for (let i = 0; i < rows; i++) {
47        for (let j = 0; j < cols; j++) {
48            // Check horizontal placement (left to right)
49            // Valid start: left boundary or blocked cell on the left
50            const canPlaceLeftToRight = (j === 0 || board[i][j - 1] === '#') && canPlaceWord(i, j, 0, 1);
51          
52            // Check horizontal placement (right to left)
53            // Valid start: right boundary or blocked cell on the right
54            const canPlaceRightToLeft = (j === cols - 1 || board[i][j + 1] === '#') && canPlaceWord(i, j, 0, -1);
55          
56            // Check vertical placement (top to bottom)
57            // Valid start: top boundary or blocked cell above
58            const canPlaceTopToBottom = (i === 0 || board[i - 1][j] === '#') && canPlaceWord(i, j, 1, 0);
59          
60            // Check vertical placement (bottom to top)
61            // Valid start: bottom boundary or blocked cell below
62            const canPlaceBottomToTop = (i === rows - 1 || board[i + 1][j] === '#') && canPlaceWord(i, j, -1, 0);
63          
64            // If word can be placed in any direction, return true
65            if (canPlaceLeftToRight || canPlaceRightToLeft || canPlaceTopToBottom || canPlaceBottomToTop) {
66                return true;
67            }
68        }
69    }
70  
71    // Word cannot be placed anywhere on the board
72    return false;
73}
74

Time and Space Complexity

The time complexity is O(m × n × k), where m and n are the number of rows and columns in the board respectively, and k is the length of the word.

The analysis breaks down as follows:

The outer loops iterate through all cells in the board: O(m × n)
For each cell, we potentially check 4 directions (left-to-right, right-to-left, up-to-down, down-to-up)
The check function iterates through each character in the word, which takes O(k) time
Therefore, the total time complexity is O(m × n × k)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space for variables like i, j, x, y, and the direction indicators. No additional data structures that scale with input size are created.

Note: The reference answer stating O(m × n) time complexity appears to be incomplete as it doesn't account for the word length k in the traversal within the check function.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Boundary Validation Before Placement

A common mistake is forgetting to check that the starting position of the word is actually at the beginning of a valid slot. Many solutions incorrectly attempt to place words in the middle of existing slots.

Incorrect approach:

# Wrong: Directly checking placement without validating the starting boundary
if can_place_word(row, col, 0, 1):  # Left-to-right
    return True

Why it fails: If there's an empty cell or letter immediately before the starting position, the word would incorrectly extend an existing slot rather than fitting exactly within boundaries.

Correct approach:

# Must verify the cell before the start is a boundary (edge or '#')
if (col == 0 or board[row][col - 1] == '#') and can_place_word(row, col, 0, 1):
    return True

2. Missing End Boundary Check

Another critical error is not verifying that the position immediately after the word ends is blocked. This would allow words to improperly merge with adjacent slots.

Incorrect approach:

def can_place_word(start_row, start_col, row_delta, col_delta):
    # Wrong: Only checking if word fits, not what comes after
    current_row, current_col = start_row, start_col
    for char in word:
        if current_row < 0 or current_row >= rows or current_col >= cols:
            return False
        if board[current_row][current_col] != ' ' and board[current_row][current_col] != char:
            return False
        current_row += row_delta
        current_col += col_delta
    return True  # Missing end boundary check!

Correct approach:

def can_place_word(start_row, start_col, row_delta, col_delta):
    # First check the end boundary
    end_row = start_row + row_delta * word_length
    end_col = start_col + col_delta * word_length
  
    # The position after the word must be out of bounds or blocked
    if 0 <= end_row < rows and 0 <= end_col < cols and board[end_row][end_col] != '#':
        return False  # Word would extend into another slot
  
    # Then validate character placement...

3. Confusing Direction Vectors

It's easy to mix up the direction vectors or use them inconsistently, especially when dealing with "reverse" directions.

Common confusion:

Mixing up row/column indices with x/y coordinates
Using (1, 0) thinking it means "right" when it actually means "down"
Incorrectly calculating positions for right-to-left or bottom-to-top directions

Clear direction mapping:

# Direction vectors: (row_delta, col_delta)
LEFT_TO_RIGHT = (0, 1)   # Row stays same, column increases
RIGHT_TO_LEFT = (0, -1)  # Row stays same, column decreases  
TOP_TO_BOTTOM = (1, 0)   # Row increases, column stays same
BOTTOM_TO_TOP = (-1, 0)  # Row decreases, column stays same

4. Edge Case: Single Character Words

For single-character words, both the start and end boundary checks become critical, as the word occupies only one cell.

Potential issue: Not handling the case where a single character word needs to fit in a single-cell slot (bounded on all relevant sides).

Solution: The existing logic handles this correctly by checking both boundaries, but it's important to test with single-character words to ensure both before and after positions are properly validated.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don't know