Check if Word Can Be Placed In Crossword - Practice Coding Problems

Check if Word Can Be Placed In Crossword - Problem

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 the board.
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.

Input & Output

Example 1 — Word Fits Vertically

$ Input: board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc"

› Output: true

💡 Note: The word "abc" can be placed vertically in column 1: board[0][1]=' ' becomes 'a', board[1][1]=' ' becomes 'b', board[2][1]='c' stays 'c'. The placement is valid as it's bounded by '#' cells.

Example 2 — Word Fits Horizontally

$ Input: board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac"

› Output: true

💡 Note: The word "ac" can be placed horizontally in row 1, columns 0-1: board[1][0]=' ' becomes 'a', board[1][1]=' ' becomes 'c'. It's properly bounded by '#' on the right.

Example 3 — No Valid Placement

$ Input: board = [["#", "#", "#"], [" ", " ", " "], ["#", "#", "#"]], word = "abc"

› Output: false

💡 Note: The word "abc" has length 3, but the only available slot is the middle row with length 3. However, there are no boundaries ('#') at the ends of this slot, so the word cannot be placed.

Constraints

m == board.length
n == board[i].length
1 ≤ m, n ≤ 20
board[i][j] will be ' ', '#', or a lowercase English letter
1 ≤ word.length ≤ max(m, n)

Visualization

Tap to expand

Understanding the Visualization

Input Board

3x3 crossword with spaces, blocked cells (#), and existing letters

Find Valid Slots

Identify continuous sequences bounded by '#' that match word length

Check Compatibility

Verify each character can be placed (empty space or matching letter)

Key Takeaway

🎯 Key Insight: Words must fit in continuous slots of exact length, bounded by '#' or board edges, with compatible characters

Asked in

G Google 12 a Amazon 8 M Microsoft 6 A Apple 4

The key insight is that a word can only be placed in continuous slots that are exactly bounded by '#' cells or board edges. The optimal approach systematically finds all valid slots of the correct length, then checks if the word characters are compatible (empty or matching). Time: O(m×n×L), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Slot Finding	O(m × n × L)	O(1)	Find valid slots first, then check if word fits in each slot
Brute Force Enumeration	O(m × n × L)	O(1)	Try placing the word at every position in all four directions

Optimized Slot Finding — Algorithm Steps

Find all horizontal slots of length >= word.length bounded by '#' or edges
Find all vertical slots of length >= word.length bounded by '#' or edges
For each valid slot, check if word can be placed (considering both directions)
Return true if any slot accepts the word

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Slots

Identify continuous sequences bounded by '#' or edges

Filter by Length

Only consider slots that match word length exactly

Check Compatibility

Test if word fits in slot (both directions)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

void reverseString(char* str, char* reversed) {
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        reversed[i] = str[len - 1 - i];
    }
    reversed[len] = '\0';
}

bool checkWordFit(char* chars, char* word, bool reverse) {
    char target[100];
    if (reverse) {
        reverseString(word, target);
    } else {
        strcpy(target, word);
    }
    
    int len = strlen(target);
    for (int i = 0; i < len; i++) {
        if (chars[i] != ' ' && chars[i] != target[i]) {
            return false;
        }
    }
    return true;
}

bool solution(char board[][100], int m, int n, char* word) {
    if (m == 0 || n == 0 || strlen(word) == 0) return false;
    
    int wordLen = strlen(word);
    
    // Check horizontal slots
    for (int i = 0; i < m; i++) {
        int j = 0;
        while (j < n) {
            if (board[i][j] != '#') {
                int start = j;
                while (j < n && board[i][j] != '#') j++;
                int slotLen = j - start;
                
                if (slotLen == wordLen) {
                    char slotChars[101];
                    for (int k = 0; k < wordLen; k++) {
                        slotChars[k] = board[i][start + k];
                    }
                    slotChars[wordLen] = '\0';
                    
                    if (checkWordFit(slotChars, word, false) || checkWordFit(slotChars, word, true)) {
                        return true;
                    }
                }
            } else {
                j++;
            }
        }
    }
    
    // Check vertical slots
    for (int j = 0; j < n; j++) {
        int i = 0;
        while (i < m) {
            if (board[i][j] != '#') {
                int start = i;
                while (i < m && board[i][j] != '#') i++;
                int slotLen = i - start;
                
                if (slotLen == wordLen) {
                    char slotChars[101];
                    for (int k = 0; k < wordLen; k++) {
                        slotChars[k] = board[start + k][j];
                    }
                    slotChars[wordLen] = '\0';
                    
                    if (checkWordFit(slotChars, word, false) || checkWordFit(slotChars, word, true)) {
                        return true;
                    }
                }
            } else {
                i++;
            }
        }
    }
    
    return false;
}

int main() {
    char board[100][100];
    char word[100];
    int m = 0, n = 0;
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char* ptr = line;
    while (*ptr && *ptr != '[') ptr++;
    if (*ptr == '[') {
        ptr++;
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                n = 0;
                while (*ptr && *ptr != ']') {
                    if (*ptr == '"') {
                        ptr++;
                        board[m][n] = *ptr;
                        n++;
                        ptr++;
                        if (*ptr == '"') ptr++;
                    }
                    if (*ptr == ',') ptr++;
                }
                if (*ptr == ']') {
                    ptr++;
                    m++;
                }
            }
            if (*ptr == ',') ptr++;
        }
    }
    
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    bool result = solution(board, m, n, word);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n × L)

Still need to scan entire board to find slots, then validate each potential placement

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for slot tracking

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Slot Finding — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler