Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Check if Word Can Be Placed In Crossword solution and explanation

MediumArrayEnumerationMatrix9 min read50.7% acceptanceUpdated 9 Apr 2026
Asked atGoogle
Practise Check if Word Can Be Placed In Crossword
8:21
Leetcode:Check if Word Can Be Placed In CrosswordCoding For Dummies · 8:21 · 1K viewsWatch on YouTube
4 more videos on this problem
  1. Leetcode:Check if Word Can Be Placed In CrosswordCoding For Dummies · 8:21 · 1K views
  2. 2018. Check if Word Can Be Placed In Crossword (Leetcode Medium)Programming Live with Larry · 22:57 · 1K views
  3. 2018 Check if Word Can Be Placed In Crossword Leetcode CPP SolutionAnimated Anand · 9:34 · 1K views
  4. 【每日一题】LeetCode 2018. Check if Word Can Be Placed In CrosswordHuifeng Guan · 19:21 · 831 views
  5. LeetCode 2018: Check if Word Can Be Placed In CrosswordAlitaCode · 26:46 · 11 views

The 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.

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.length
  • n == board[i].length
  • 1 <= m * n <= 2 * 105
  • board[i][j] will be ' ', '#', or a lowercase English letter.
  • 1 <= word.length <= max(m, n)
  • word will 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.

Approach 1: Greedy Check for Each Row and Column

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.

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        wordLen = len(word)

        def checkRow(row, col):
            if col + wordLen <= n and (col == 0 or board[row][col - 1] == '#') and (col + wordLen == n or board[row][col + wordLen] == '#'):
                if all(board[row][col + k] in [' ', word[k]] for k in range(wordLen)):
                    return True
            if col - wordLen + 1 >= 0 and (col == n - 1 or board[row][col + 1] == '#') and (col - wordLen + 1 == 0 or board[row][col - wordLen] == '#'):
                if all(board[row][col - k] in [' ', word[k]] for k in range(wordLen)):
                    return True
            return False

        def checkCol(row, col):
            if row + wordLen <= m and (row == 0 or board[row - 1][col] == '#') and (row + wordLen == m or board[row + wordLen][col] == '#'):
                if all(board[row + k][col] in [' ', word[k]] for k in range(wordLen)):
                    return True
            if row - wordLen + 1 >= 0 and (row == m - 1 or board[row + 1][col] == '#') and (row - wordLen + 1 == 0 or board[row - wordLen][col] == '#'):
                if all(board[row - k][col] in [' ', word[k]] for k in range(wordLen)):
                    return True
            return False

        for i in range(m):
            for j in range(n):
                if checkRow(i, j) or checkCol(i, j):
                    return True
        return False
public class Solution {
    public boolean placeWordInCrossword(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        int wordLen = word.length();
        char[] wordArr = word.toCharArray();
        // Horizontal check
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (checkRow(board, i, j, n, wordArr, wordLen)) return true;
            }
        }
        // Vertical check
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                if (checkCol(board, i, j, m, wordArr, wordLen)) return true;
            }
        }
        return false;
    }

    private boolean checkRow(char[][] board, int row, int col, int n, char[] wordArr, int wordLen) {
        if (col + wordLen <= n) {
            boolean canPlace = true;
            if (col > 0 && board[row][col - 1] != '#') canPlace = false;
            for (int k = 0; k < wordLen && canPlace; ++k) {
                if (board[row][col + k] != ' ' && board[row][col + k] != wordArr[k]) canPlace = false;
            }
            if (canPlace && (col + wordLen == n || board[row][col + wordLen] == '#')) return true;
        }
        if (col - wordLen + 1 >= 0) {
            boolean canPlace = true;
            if (col < n - 1 && board[row][col + 1] != '#') canPlace = false;
            for (int k = 0; k < wordLen && canPlace; ++k) {
                if (board[row][col - k] != ' ' && board[row][col - k] != wordArr[k]) canPlace = false;
            }
            if (canPlace && (col - wordLen + 1 == 0 || board[row][col - wordLen] == '#')) return true;
        }
        return false;
    }

    private boolean checkCol(char[][] board, int row, int col, int m, char[] wordArr, int wordLen) {
        if (row + wordLen <= m) {
            boolean canPlace = true;
            if (row > 0 && board[row - 1][col] != '#') canPlace = false;
            for (int k = 0; k < wordLen && canPlace; ++k) {
                if (board[row + k][col] != ' ' && board[row + k][col] != wordArr[k]) canPlace = false;
            }
            if (canPlace && (row + wordLen == m || board[row + wordLen][col] == '#')) return true;
        }
        if (row - wordLen + 1 >= 0) {
            boolean canPlace = true;
            if (row < m - 1 && board[row + 1][col] != '#') canPlace = false;
            for (int k = 0; k < wordLen && canPlace; ++k) {
                if (board[row - k][col] != ' ' && board[row - k][col] != wordArr[k]) canPlace = false;
            }
            if (canPlace && (row - wordLen + 1 == 0 || board[row - wordLen][col] == '#')) return true;
        }
        return false;
    }
}
#include <vector>
#include <string>

using namespace std;

bool checkRow(const vector<vector<char>>& board, int row, int col, const string& word, int wordLen) {
    int n = board[0].size();
    if (col + wordLen <= n) {
        bool canPlace = true;
        if (col > 0 && board[row][col - 1] != '#') canPlace = false;
        for (int k = 0; k < wordLen && canPlace; ++k) {
            if (board[row][col + k] != ' ' && board[row][col + k] != word[k]) canPlace = false;
        }
        if (canPlace && (col + wordLen == n || board[row][col + wordLen] == '#')) return true;
    }
    if (col - wordLen + 1 >= 0) {
        bool canPlace = true;
        if (col < n - 1 && board[row][col + 1] != '#') canPlace = false;
        for (int k = 0; k < wordLen && canPlace; ++k) {
            if (board[row][col - k] != ' ' && board[row][col - k] != word[k]) canPlace = false;
        }
        if (canPlace && (col - wordLen + 1 == 0 || board[row][col - wordLen] == '#')) return true;
    }
    return false;
}

bool checkCol(const vector<vector<char>>& board, int row, int col, const string& word, int wordLen) {
    int m = board.size();
    if (row + wordLen <= m) {
        bool canPlace = true;
        if (row > 0 && board[row - 1][col] != '#') canPlace = false;
        for (int k = 0; k < wordLen && canPlace; ++k) {
            if (board[row + k][col] != ' ' && board[row + k][col] != word[k]) canPlace = false;
        }
        if (canPlace && (row + wordLen == m || board[row + wordLen][col] == '#')) return true;
    }
    if (row - wordLen + 1 >= 0) {
        bool canPlace = true;
        if (row < m - 1 && board[row + 1][col] != '#') canPlace = false;
        for (int k = 0; k < wordLen && canPlace; ++k) {
            if (board[row - k][col] != ' ' && board[row - k][col] != word[k]) canPlace = false;
        }
        if (canPlace && (row - wordLen + 1 == 0 || board[row - wordLen][col] == '#')) return true;
    }
    return false;
}

bool placeWordInCrossword(vector<vector<char>>& board, const string& word) {
    int m = board.size();
    int n = board[0].size();
    int wordLen = word.length();
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (checkRow(board, i, j, word, wordLen)) return true;
        }
    }
    for (int j = 0; j < n; ++j) {
        for (int i = 0; i < m; ++i) {
            if (checkCol(board, i, j, word, wordLen)) return true;
        }
    }
    return false;
}
var placeWordInCrossword = function(board, word) {
    const m = board.length, n = board[0].length;
    const wordLen = word.length;

    function checkRow(row, col) {
        if (col + wordLen <= n && (col === 0 || board[row][col - 1] === '#') && (col + wordLen === n || board[row][col + wordLen] === '#')) {
            let canPlace = true;
            for (let k = 0; k < wordLen && canPlace; k++) {
                if (board[row][col + k] !== ' ' && board[row][col + k] !== word[k]) canPlace = false;
            }
            if (canPlace) return true;
        }
        if (col - wordLen + 1 >= 0 && (col === n - 1 || board[row][col + 1] === '#') && (col - wordLen + 1 === 0 || board[row][col - wordLen] === '#')) {
            let canPlace = true;
            for (let k = 0; k < wordLen && canPlace; k++) {
                if (board[row][col - k] !== ' ' && board[row][col - k] !== word[k]) canPlace = false;
            }
            if (canPlace) return true;
        }
        return false;
    }

    function checkCol(row, col) {
        if (row + wordLen <= m && (row === 0 || board[row - 1][col] === '#') && (row + wordLen === m || board[row + wordLen][col] === '#')) {
            let canPlace = true;
            for (let k = 0; k < wordLen && canPlace; k++) {
                if (board[row + k][col] !== ' ' && board[row + k][col] !== word[k]) canPlace = false;
            }
            if (canPlace) return true;
        }
        if (row - wordLen + 1 >= 0 && (row === m - 1 || board[row + 1][col] === '#') && (row - wordLen + 1 === 0 || board[row - wordLen][col] === '#')) {
            let canPlace = true;
            for (let k = 0; k < wordLen && canPlace; k++) {
                if (board[row - k][col] !== ' ' && board[row - k][col] !== word[k]) canPlace = false;
            }
            if (canPlace) return true;
        }
        return false;
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (checkRow(i, j) || checkCol(i, j)) return true;
        }
    }
    return false;
};
#include <stdbool.h>
#include <string.h>

bool checkRow(char** board, int row, int col, int m, int n, const char* word, int wordLen) {
    // Left to Right
    if (col + wordLen <= n) {
        bool canPlace = true;
        if (col > 0 && board[row][col - 1] != '#') canPlace = false;  // Check left boundary
        for (int k = 0; k < wordLen && canPlace; ++k) {
            if (board[row][col + k] != ' ' && board[row][col + k] != word[k]) canPlace = false;
        }
        if (canPlace && (col + wordLen == n || board[row][col + wordLen] == '#')) return true;
    }
    // Right to Left
    if (col - wordLen + 1 >= 0) {
        bool canPlace = true;
        if (col < n - 1 && board[row][col + 1] != '#') canPlace = false;  // Check right boundary
        for (int k = 0; k < wordLen && canPlace; ++k) {
            if (board[row][col - k] != ' ' && board[row][col - k] != word[k]) canPlace = false;
        }
        if (canPlace && (col - wordLen + 1 == 0 || board[row][col - wordLen] == '#')) return true;
    }
    return false;
}

bool checkCol(char** board, int row, int col, int m, int n, const char* word, int wordLen) {
    // Top to Bottom
    if (row + wordLen <= m) {
        bool canPlace = true;
        if (row > 0 && board[row - 1][col] != '#') canPlace = false;  // Check top boundary
        for (int k = 0; k < wordLen && canPlace; ++k) {
            if (board[row + k][col] != ' ' && board[row + k][col] != word[k]) canPlace = false;
        }
        if (canPlace && (row + wordLen == m || board[row + wordLen][col] == '#')) return true;
    }
    // Bottom to Top
    if (row - wordLen + 1 >= 0) {
        bool canPlace = true;
        if (row < m - 1 && board[row + 1][col] != '#') canPlace = false;  // Check bottom boundary
        for (int k = 0; k < wordLen && canPlace; ++k) {
            if (board[row - k][col] != ' ' && board[row - k][col] != word[k]) canPlace = false;
        }
        if (canPlace && (row - wordLen + 1 == 0 || board[row - wordLen][col] == '#')) return true;
    }
    return false;
}

bool placeWordInCrossword(char** board, int m, int n, const char* word) {
    int wordLen = strlen(word);
    // Check by row
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (checkRow(board, i, j, m, n, word, wordLen)) return true;
        }
    }
    // Check by column
    for (int j = 0; j < n; ++j) {
        for (int i = 0; i < m; ++i) {
            if (checkCol(board, i, j, m, n, word, wordLen)) return true;
        }
    }
    return false;
}
public class Solution {
    public bool PlaceWordInCrossword(char[][] board, string word) {
        int m = board.Length, n = board[0].Length;
        int wordLen = word.Length;

        bool CheckRow(int row, int col) {
            if (col + wordLen <= n) {
                bool canPlace = true;
                if (col > 0 && board[row][col - 1] != '#') canPlace = false;
                for (int k = 0; k < wordLen && canPlace; ++k) {
                    if (board[row][col + k] != ' ' && board[row][col + k] != word[k]) canPlace = false;
                }
                if (canPlace && (col + wordLen == n || board[row][col + wordLen] == '#')) return true;
            }
            if (col - wordLen + 1 >= 0) {
                bool canPlace = true;
                if (col < n - 1 && board[row][col + 1] != '#') canPlace = false;
                for (int k = 0; k < wordLen && canPlace; ++k) {
                    if (board[row][col - k] != ' ' && board[row][col - k] != word[k]) canPlace = false;
                }
                if (canPlace && (col - wordLen + 1 == 0 || board[row][col - wordLen] == '#')) return true;
            }
            return false;
        }

        bool CheckCol(int row, int col) {
            if (row + wordLen <= m) {
                bool canPlace = true;
                if (row > 0 && board[row - 1][col] != '#') canPlace = false;
                for (int k = 0; k < wordLen && canPlace; ++k) {
                    if (board[row + k][col] != ' ' && board[row + k][col] != word[k]) canPlace = false;
                }
                if (canPlace && (row + wordLen == m || board[row + wordLen][col] == '#')) return true;
            }
            if (row - wordLen + 1 >= 0) {
                bool canPlace = true;
                if (row < m - 1 && board[row + 1][col] != '#') canPlace = false;
                for (int k = 0; k < wordLen && canPlace; ++k) {
                    if (board[row - k][col] != ' ' && board[row - k][col] != word[k]) canPlace = false;
                }
                if (canPlace && (row - wordLen + 1 == 0 || board[row - wordLen][col] == '#')) return true;
            }
            return false;
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (CheckRow(i, j) || CheckCol(i, j)) return true;
            }
        }
        return false;
    }
}

In the Python solution, helper functions are defined for checking row and column placements, ensuring that constraints are met for empty or matched spaces as per the rules.

Complexity

Time Complexity: O(m * n * max(m, n)).
Space Complexity: O(1), disregarding input size.

Try this approach in the editor

Approach 2: Advanced Optimized Inline Check

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.

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        wordLen = len(word)

        for i in range(m):
            for j in range(n):
                if board[i][j] in [' ', word[0]]:
                    # horizontal-right
                    if j + wordLen <= n and (j == 0 or board[i][j - 1] == '#') and (j + wordLen == n or board[i][j + wordLen] == '#'):
                        if all(board[i][j + k] in [' ', word[k]] for k in range(wordLen)):
                            return True
                    # horizontal-left
                    if j - wordLen + 1 >= 0 and (j == n - 1 or board[i][j + 1] == '#') and (j - wordLen + 1 == 0 or board[i][j - wordLen] == '#'):
                        if all(board[i][j - k] in [' ', word[k]] for k in range(wordLen)):
                            return True
                if board[i][j] in [' ', word[0]]:
                    # vertical-down
                    if i + wordLen <= m and (i == 0 or board[i - 1][j] == '#') and (i + wordLen == m or board[i + wordLen][j] == '#'):
                        if all(board[i + k][j] in [' ', word[k]] for k in range(wordLen)):
                            return True
                    # vertical-up
                    if i - wordLen + 1 >= 0 and (i == m - 1 or board[i + 1][j] == '#') and (i - wordLen + 1 == 0 or board[i - wordLen][j] == '#'):
                        if all(board[i - k][j] in [' ', word[k]] for k in range(wordLen)):
                            return True
        return False
public class Solution {
    public boolean placeWordInCrossword(char[][] board, String word) {
        int m = board.length, n = board[0].length, wordLen = word.length();

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == ' ' || board[i][j] == word.charAt(0)) {
                    if (j + wordLen <= n && (j == 0 || board[i][j - 1] == '#') && (j + wordLen == n || board[i][j + wordLen] == '#')) {
                        boolean valid = true;
                        for (int k = 0; k < wordLen && valid; ++k) {
                            if (board[i][j + k] != ' ' && board[i][j + k] != word.charAt(k)) valid = false;
                        }
                        if (valid) return true;
                    }
                    if (j - wordLen + 1 >= 0 && (j == n - 1 || board[i][j + 1] == '#') && (j - wordLen + 1 == 0 || board[i][j - wordLen] == '#')) {
                        boolean valid = true;
                        for (int k = 0; k < wordLen && valid; ++k) {
                            if (board[i][j - k] != ' ' && board[i][j - k] != word.charAt(k)) valid = false;
                        }
                        if (valid) return true;
                    }
                }
                if (board[i][j] == ' ' || board[i][j] == word.charAt(0)) {
                    if (i + wordLen <= m && (i == 0 || board[i - 1][j] == '#') && (i + wordLen == m || board[i + wordLen][j] == '#')) {
                        boolean valid = true;
                        for (int k = 0; k < wordLen && valid; ++k) {
                            if (board[i + k][j] != ' ' && board[i + k][j] != word.charAt(k)) valid = false;
                        }
                        if (valid) return true;
                    }
                    if (i - wordLen + 1 >= 0 && (i == m - 1 || board[i + 1][j] == '#') && (i - wordLen + 1 == 0 || board[i - wordLen][j] == '#')) {
                        boolean valid = true;
                        for (int k = 0; k < wordLen && valid; ++k) {
                            if (board[i - k][j] != ' ' && board[i - k][j] != word.charAt(k)) valid = false;
                        }
                        if (valid) return true;
                    }
                }
            }
        }
        return false;
    }
}
#include <vector>
#include <string>

bool placeWordInCrossword(std::vector<std::vector<char>>& board, std::string word) {
    int m = board.size(), n = board[0].size(), wordLen = word.length();

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((board[i][j] == ' ' || board[i][j] == word[0])) {
                // horizontal right
                if (j + wordLen <= n && (j == 0 || board[i][j - 1] == '#') && (j + wordLen == n || board[i][j + wordLen] == '#')) {
                    bool valid = true;
                    for (int k = 0; k < wordLen && valid; ++k) {
                        if (board[i][j + k] != ' ' && board[i][j + k] != word[k]) valid = false;
                    }
                    if (valid) return true;
                }
                // horizontal left
                if (j - wordLen + 1 >= 0 && (j == n - 1 || board[i][j + 1] == '#') && (j - wordLen + 1 == 0 || board[i][j - wordLen] == '#')) {
                    bool valid = true;
                    for (int k = 0; k < wordLen && valid; ++k) {
                        if (board[i][j - k] != ' ' && board[i][j - k] != word[k]) valid = false;
                    }
                    if (valid) return true;
                }
            }
            if ((board[i][j] == ' ' || board[i][j] == word[0])) {
                // vertical down
                if (i + wordLen <= m && (i == 0 || board[i - 1][j] == '#') && (i + wordLen == m || board[i + wordLen][j] == '#')) {
                    bool valid = true;
                    for (int k = 0; k < wordLen && valid; ++k) {
                        if (board[i + k][j] != ' ' && board[i + k][j] != word[k]) valid = false;
                    }
                    if (valid) return true;
                }
                // vertical up
                if (i - wordLen + 1 >= 0 && (i == m - 1 || board[i + 1][j] == '#') && (i - wordLen + 1 == 0 || board[i - wordLen][j] == '#')) {
                    bool valid = true;
                    for (int k = 0; k < wordLen && valid; ++k) {
                        if (board[i - k][j] != ' ' && board[i - k][j] != word[k]) valid = false;
                    }
                    if (valid) return true;
                }
            }
        }
    }
    return false;
}
var placeWordInCrossword = function(board, word) {
    const m = board.length, n = board[0].length;
    const wordLen = word.length;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === ' ' || board[i][j] === word[0]) {
                // horizontal-right
                if (j + wordLen <= n && (j === 0 || board[i][j - 1] === '#') && (j + wordLen === n || board[i][j + wordLen] === '#')) {
                    let valid = true;
                    for (let k = 0; k < wordLen && valid; k++) {
                        if (board[i][j + k] !== ' ' && board[i][j + k] !== word[k]) valid = false;
                    }
                    if (valid) return true;
                }
                // horizontal-left
                if (j - wordLen + 1 >= 0 && (j === n - 1 || board[i][j + 1] === '#') && (j - wordLen + 1 === 0 || board[i][j - wordLen] === '#')) {
                    let valid = true;
                    for (let k = 0; k < wordLen && valid; k++) {
                        if (board[i][j - k] !== ' ' && board[i][j - k] !== word[k]) valid = false;
                    }
                    if (valid) return true;
                }
            }
            if (board[i][j] === ' ' || board[i][j] === word[0]) {
                // vertical-down
                if (i + wordLen <= m && (i === 0 || board[i - 1][j] === '#') && (i + wordLen === m || board[i + wordLen][j] === '#')) {
                    let valid = true;
                    for (let k = 0; k < wordLen && valid; k++) {
                        if (board[i + k][j] !== ' ' && board[i + k][j] !== word[k]) valid = false;
                    }
                    if (valid) return true;
                }
                // vertical-up
                if (i - wordLen + 1 >= 0 && (i === m - 1 || board[i + 1][j] === '#') && (i - wordLen + 1 === 0 || board[i - wordLen][j] === '#')) {
                    let valid = true;
                    for (let k = 0; k < wordLen && valid; k++) {
                        if (board[i - k][j] !== ' ' && board[i - k][j] !== word[k]) valid = false;
                    }
                    if (valid) return true;
                }
            }
        }
    }
    return false;
};
#include <stdbool.h>
#include <string.h>

bool placeWordInCrossword(char** board, int rowSize, int* colSize, const char* word) {
    int m = rowSize, n = colSize[0], wordLen = strlen(word);

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((board[i][j] == ' ' || board[i][j] == word[0])) {
                // horizontal-right
                if (j + wordLen <= n && (j == 0 || board[i][j - 1] == '#') && (j + wordLen == n || board[i][j + wordLen] == '#')) {
                    bool valid = true;
                    for (int k = 0; k < wordLen && valid; ++k) {
                        if (board[i][j + k] != ' ' && board[i][j + k] != word[k]) valid = false;
                    }
                    if (valid) return true;
                }
                // horizontal-left
                if (j - wordLen + 1 >= 0 && (j == n - 1 || board[i][j + 1] == '#') && (j - wordLen + 1 == 0 || board[i][j - wordLen] == '#')) {
                    bool valid = true;
                    for (int k = 0; k < wordLen && valid; ++k) {
                        if (board[i][j - k] != ' ' && board[i][j - k] != word[k]) valid = false;
                    }
                    if (valid) return true;
                }
            }
            if ((board[i][j] == ' ' || board[i][j] == word[0])) {
                // vertical-down
                if (i + wordLen <= m && (i == 0 || board[i - 1][j] == '#') && (i + wordLen == m || board[i + wordLen][j] == '#')) {
                    bool valid = true;
                    for (int k = 0; k < wordLen && valid; ++k) {
                        if (board[i + k][j] != ' ' && board[i + k][j] != word[k]) valid = false;
                    }
                    if (valid) return true;
                }
                // vertical-up
                if (i - wordLen + 1 >= 0 && (i == m - 1 || board[i + 1][j] == '#') && (i - wordLen + 1 == 0 || board[i - wordLen][j] == '#')) {
                    bool valid = true;
                    for (int k = 0; k < wordLen && valid; ++k) {
                        if (board[i - k][j] != ' ' && board[i - k][j] != word[k]) valid = false;
                    }
                    if (valid) return true;
                }
            }
        }
    }
    return false;
}
public class Solution {
    public bool PlaceWordInCrossword(char[][] board, string word) {
        int m = board.Length, n = board[0].Length, wordLen = word.Length;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == ' ' || board[i][j] == word[0]) {
                    // horizontal right
                    if (j + wordLen <= n && (j == 0 || board[i][j - 1] == '#') && (j + wordLen == n || board[i][j + wordLen] == '#')) {
                        bool valid = true;
                        for (int k = 0; k < wordLen && valid; ++k) {
                            if (board[i][j + k] != ' ' && board[i][j + k] != word[k]) valid = false;
                        }
                        if (valid) return true;
                    }
                    // horizontal left
                    if (j - wordLen + 1 >= 0 && (j == n - 1 || board[i][j + 1] == '#') && (j - wordLen + 1 == 0 || board[i][j - wordLen] == '#')) {
                        bool valid = true;
                        for (int k = 0; k < wordLen && valid; ++k) {
                            if (board[i][j - k] != ' ' && board[i][j - k] != word[k]) valid = false;
                        }
                        if (valid) return true;
                    }
                }
                if (board[i][j] == ' ' || board[i][j] == word[0]) {
                    // vertical down
                    if (i + wordLen <= m && (i == 0 || board[i - 1][j] == '#') && (i + wordLen == m || board[i + wordLen][j] == '#')) {
                        bool valid = true;
                        for (int k = 0; k < wordLen && valid; ++k) {
                            if (board[i + k][j] != ' ' && board[i + k][j] != word[k]) valid = false;
                        }
                        if (valid) return true;
                    }
                    // vertical up
                    if (i - wordLen + 1 >= 0 && (i == m - 1 || board[i + 1][j] == '#') && (i - wordLen + 1 == 0 || board[i - wordLen][j] == '#')) {
                        bool valid = true;
                        for (int k = 0; k < wordLen && valid; ++k) {
                            if (board[i - k][j] != ' ' && board[i - k][j] != word[k]) valid = false;
                        }
                        if (valid) return true;
                    }
                }
            }
        }
        return false;
    }
}

In this Python approach, use of inline segmented checks reduces redundant checks through inline verification strategies, improving efficiency.

Complexity

Time Complexity: O(m * n * max(m, n)) where m is the number of rows and n is the number of columns.
Space Complexity: O(1).

Try this approach in the editor

Approach 3: Enumeration

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:

  1. If the word 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 '#'.
  2. If the word 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 '#'.
  3. If the word 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 '#'.
  4. If the word 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.

func placeWordInCrossword(board [][]byte, word string) bool {
	m, n := len(board), len(board[0])
	k := len(word)
	check := func(i, j, a, b int) bool {
		x, y := i+a*k, j+b*k
		if x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '#' {
			return false
		}
		for _, c := range word {
			if i < 0 || i >= m || j < 0 || j >= n || (board[i][j] != ' ' && board[i][j] != byte(c)) {
				return false
			}
			i, j = i+a, j+b
		}
		return true
	}
	for i := range board {
		for j := range board[i] {
			leftToRight := (j == 0 || board[i][j-1] == '#') && check(i, j, 0, 1)
			rightToLeft := (j == n-1 || board[i][j+1] == '#') && check(i, j, 0, -1)
			upToDown := (i == 0 || board[i-1][j] == '#') && check(i, j, 1, 0)
			downToUp := (i == m-1 || board[i+1][j] == '#') && check(i, j, -1, 0)
			if leftToRight || rightToLeft || upToDown || downToUp {
				return true
			}
		}
	}
	return false
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Greedy Check for Each Row and Column

Time Complexity: O(m * n * max(m, n)).
Space Complexity: O(1), disregarding input size.

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.
Space Complexity: O(1).

Enumeration–

Complexity analysis

ApproachTimeSpaceWhen to Use
Greedy Check for Each Row and ColumnO(m * n * k)O(1)Clear and straightforward implementation when explaining the slot matching idea
Advanced Optimized Inline CheckO(m * n)O(1)Preferred interview solution when you want a single linear traversal of the grid

Frequently asked questions

Is Check if Word Can Be Placed In Crossword easy or hard?

The problem is rated Medium because the logic is simple but edge cases can break naive solutions. Handling boundaries, reversed placement, and ensuring the word fits exactly between '#' blocks requires careful condition checks.

Check if Word Can Be Placed In Crossword Python/Java solution

Python, Java, C++, and other languages implement the same idea: iterate through the grid, detect valid starting positions, and check character matches inline. Because the algorithm only uses index traversal and simple comparisons, the code remains short and language independent.

How to solve Check if Word Can Be Placed In Crossword in O(n)?

Treat the board as a matrix scan and detect valid starting points for horizontal and vertical placements. Ensure the previous cell is a boundary or '#', then verify the next k cells match the word or are blank. Also ensure the cell immediately after the segment is blocked or out of bounds. This eliminates repeated segment scanning and keeps traversal linear across the grid.

What is the best approach for Check if Word Can Be Placed In Crossword?

The optimized inline scan is the best approach. Traverse the grid and treat each valid cell as a potential start of a word if the previous cell in that direction is a boundary or '#'. Then check exactly k cells for a forward or reversed match. This keeps the complexity at O(m * n) with O(1) extra space.

Is Check if Word Can Be Placed In Crossword asked at Google/Amazon/Meta?

Matrix scanning and constraint validation problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests grid traversal, boundary checks, and careful handling of edge cases rather than complex data structures.

What data structure is used in Check if Word Can Be Placed In Crossword?

The main data structure is a 2D matrix (grid). The algorithm performs direct index checks and enumeration across rows and columns while comparing characters with the target word.

What is the time complexity of Check if Word Can Be Placed In Crossword?

The optimized solution runs in O(m * n) time where m and n are the grid dimensions. Each cell is considered as a possible starting point at most once per direction. Space complexity remains O(1) because the algorithm only performs inline checks without additional data structures.

Comments

Now write it yourselfClose this page and solve Check if Word Can Be Placed In Crossword in the editor, without looking.
Practise Check if Word Can Be Placed In Crossword