# Check if Word Can Be Placed In Crossword
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-if-word-can-be-placed-in-crossword)
Canonical: https://scaleengineer.com/dsa/problems/check-if-word-can-be-placed-in-crossword
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Matrix
---
## 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:**

![](https://assets.glich.co/dsa/check-if-word-can-be-placed-in-crossword/image0.png) 

**Input:** board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc"
**Output:** true
**Explanation:** The word "abc" can be placed as shown above (top to bottom).

**Example 2:**

![](https://assets.glich.co/dsa/check-if-word-can-be-placed-in-crossword/image1.png) 

**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:**

![](https://assets.glich.co/dsa/check-if-word-can-be-placed-in-crossword/image2.png) 

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

# Approaches
## Brute-Force Iteration
This approach iterates through every cell of the crossword board. For each cell, it attempts to place the given `word` (and its reversed version) in all four possible directions: horizontally left-to-right, horizontally right-to-left, vertically top-to-bottom, and vertically bottom-to-top. It meticulously checks if each potential placement is valid according to all the rules specified in the problem.
**Time:** O(m * n * k), where `m` is the number of rows, `n` is the number of columns, and `k` is the length of the word. The nested loops iterate through all `m * n` cells. From each cell, the `canPlace` helper function might be called, which takes `O(k)` time to check the placement. · **Space:** O(k), where `k` is the length of the `word`. This space is used to store the reversed version of the word.
**Pros:** Simple to understand and implement as it directly translates the problem's conditions into code.; It is guaranteed to be correct as it exhaustively checks all possibilities.
**Cons:** Inefficient due to redundant computations. The same potential slot might be evaluated multiple times from different starting cells within that slot.; The time complexity of `O(m * n * k)` can be slow for large boards or long words.
### Explanation
The algorithm systematically checks every possible starting position `(r, c)` on the board. For a position to be a valid start of a word placement, it must be preceded by a board boundary or a blocked cell ('#'). This is to satisfy the rule that no empty cells or letters can be adjacent to the placed word.

For each valid starting position, we try to place both the `word` and its reverse. A helper function, `canPlace`, is used to verify if a word of length `k` can be placed starting at `(r, c)` in a specific direction. This function checks three conditions:
1. The word must stay within the board boundaries.
2. The word must end at a board boundary or be followed by a blocked cell.
3. Each character of the word must match the corresponding cell on the board, or the cell must be empty (' ').

If any of these checks succeed, the function immediately returns `true`. If all possibilities are exhausted without a valid placement, it returns `false`.

```java
class Solution {
    public boolean placeWordInCrossword(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        String reversedWord = new StringBuilder(word).reverse().toString();

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                // Check horizontal placement from (r, c)
                if (c == 0 || board[r][c - 1] == '#') {
                    if (canPlace(board, r, c, word, true) || canPlace(board, r, c, reversedWord, true)) {
                        return true;
                    }
                }
                // Check vertical placement from (r, c)
                if (r == 0 || board[r - 1][c] == '#') {
                    if (canPlace(board, r, c, word, false) || canPlace(board, r, c, reversedWord, false)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean canPlace(char[][] board, int r, int c, String word, boolean isHorizontal) {
        int m = board.length;
        int n = board[0].length;
        int k = word.length();

        if (isHorizontal) {
            if (c + k > n) return false;
            if (c + k < n && board[r][c + k] != '#') return false;
            for (int i = 0; i < k; i++) {
                char boardChar = board[r][c + i];
                char wordChar = word.charAt(i);
                if (boardChar == '#' || (boardChar != ' ' && boardChar != wordChar)) {
                    return false;
                }
            }
        } else { // isVertical
            if (r + k > m) return false;
            if (r + k < m && board[r + k][c] != '#') return false;
            for (int i = 0; i < k; i++) {
                char boardChar = board[r + i][c];
                char wordChar = word.charAt(i);
                if (boardChar == '#' || (boardChar != ' ' && boardChar != wordChar)) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
1. Get the dimensions `m` and `n` of the board, and the length `k` of the `word`.
2. Create the reversed version of the word, `reversedWord`.
3. Iterate through each cell `(r, c)` from `(0, 0)` to `(m-1, n-1)`.
4. For each cell `(r, c)`:
    - **Check Horizontal Placement:**
        - Check if the cell is a valid starting point for a horizontal word (i.e., `c == 0` or `board[r][c-1] == '#'`).
        - If it is, call a helper function `canPlace` to check if `word` or `reversedWord` can be placed horizontally starting at `(r, c)`.
        - The `canPlace` function must verify that the word fits within the board, matches existing letters, and is correctly bounded at its end.
        - If a valid placement is found, return `true`.
    - **Check Vertical Placement:**
        - Check if the cell is a valid starting point for a vertical word (i.e., `r == 0` or `board[r-1][c] == '#'`).
        - If it is, use the `canPlace` helper to check for `word` and `reversedWord` vertically.
        - If a valid placement is found, return `true`.
5. If the loops complete without finding any valid placement, return `false`.

## Optimized Slot-Based Search
This approach significantly improves efficiency by scanning the board to identify valid "slots" for word placement, rather than attempting a placement from every single cell. A slot is a contiguous sequence of non-blocked cells ('#') that is properly bounded by blocked cells or the board's edges. By focusing only on these valid slots, we eliminate a vast number of redundant checks.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. The algorithm scans the board twice (once horizontally, once vertically). In each scan, every cell is visited a constant number of times, leading to linear time complexity. · **Space:** O(k), where `k` is the length of the `word`. This space is used to store the reversed version of the word. The space used by loop variables is constant.
**Pros:** Highly efficient with a linear time complexity with respect to the board size.; Optimal space complexity, using only a small amount of extra space for the reversed word.; Avoids redundant checks by processing each potential slot exactly once.
**Cons:** The implementation can be slightly more complex than the brute-force approach due to the logic for finding segments and advancing iterators.
### Explanation
The algorithm performs two main scans of the board: one for horizontal slots and one for vertical slots.

**Horizontal Scan**: It iterates through each row. For each row, it finds contiguous segments of non-'#' characters. These segments are the only possible places a word can be placed horizontally, as they are naturally bounded by '#' or the board edges.

For each segment found, it checks if its length is exactly equal to the length of the `word`. If the lengths match, it then verifies if the `word` or its reversed version can fit into that slot. A word fits if for every character, the corresponding board cell is either empty (' ') or already contains the same character.

To be efficient, after processing a segment, the scan continues from the end of that segment, ensuring each cell is visited only a constant number of times.

**Vertical Scan**: A similar process is repeated for columns to find and check all vertical slots.

If a valid placement is found at any point, the function immediately returns `true`. If both scans complete without finding a suitable slot, it returns `false`. This method achieves linear time complexity with minimal extra space.

```java
class Solution {
    public boolean placeWordInCrossword(char[][] board, String word) {
        int m = board.length;
        int n = board[0].length;
        int k = word.length();
        String reversedWord = new StringBuilder(word).reverse().toString();

        // Horizontal check
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (board[r][c] != '#') {
                    int cStart = c;
                    while (c < n && board[r][c] != '#') {
                        c++;
                    }
                    int len = c - cStart;
                    if (len == k) {
                        if (canFitHorizontal(board, r, cStart, word) || canFitHorizontal(board, r, cStart, reversedWord)) {
                            return true;
                        }
                    }
                }
            }
        }

        // Vertical check
        for (int c = 0; c < n; c++) {
            for (int r = 0; r < m; r++) {
                if (board[r][c] != '#') {
                    int rStart = r;
                    while (r < m && board[r][c] != '#') {
                        r++;
                    }
                    int len = r - rStart;
                    if (len == k) {
                        if (canFitVertical(board, rStart, c, word) || canFitVertical(board, rStart, c, reversedWord)) {
                            return true;
                        }
                    }
                }
            }
        }

        return false;
    }

    private boolean canFitHorizontal(char[][] board, int r, int c, String word) {
        for (int i = 0; i < word.length(); i++) {
            if (board[r][c + i] != ' ' && board[r][c + i] != word.charAt(i)) {
                return false;
            }
        }
        return true;
    }

    private boolean canFitVertical(char[][] board, int r, int c, String word) {
        for (int i = 0; i < word.length(); i++) {
            if (board[r + i][c] != ' ' && board[r + i][c] != word.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
1. Get board dimensions `m`, `n` and word length `k`.
2. Create a reversed version of the `word`.
3. **Horizontal Scan**:
    - For each row `r` from `0` to `m-1`:
        - Iterate through the columns `c` from `0` to `n-1`.
        - If `board[r][c] != '#'`: 
            - This marks the start of a potential slot. Find its end `c_end` by scanning right until a '#' or the board edge is hit.
            - Calculate the slot's length. If it equals `k`:
                - Check if `word` or the `reversed word` can fit in this horizontal slot.
                - If either fits, return `true`.
            - Advance the column iterator `c` to `c_end` to skip the already-checked segment.
4. **Vertical Scan**:
    - For each column `c` from `0` to `n-1`:
        - Apply the same logic as the horizontal scan, but iterating through rows `r` to find and check vertical slots.
        - If a fit is found, return `true`.
5. If all scans complete, return `false`.

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  char[][] board;
private
  String word;
private
  int k;
public
  boolean placeWordInCrossword(char[][] board, String word) {
    m = board.length;
    n = board[0].length;
    this.board = board;
    this.word = word;
    k = word.length();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        boolean leftToRight =
            (j == 0 || board[i][j - 1] == '#') && check(i, j, 0, 1);
        boolean rightToLeft =
            (j == n - 1 || board[i][j + 1] == '#') && check(i, j, 0, -1);
        boolean upToDown =
            (i == 0 || board[i - 1][j] == '#') && check(i, j, 1, 0);
        boolean downToUp =
            (i == m - 1 || board[i + 1][j] == '#') && check(i, j, -1, 0);
        if (leftToRight || rightToLeft || upToDown || downToUp) {
          return true;
        }
      }
    }
    return false;
  }
private
  boolean check(int i, int j, int a, int b) {
    int x = i + a * k, y = j + b * k;
    if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '#') {
      return false;
    }
    for (int p = 0; p < k; ++p) {
      if (i < 0 || i >= m || j < 0 || j >= n ||
          (board[i][j] != ' ' && board[i][j] != word.charAt(p))) {
        return false;
      }
      i += a;
      j += b;
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution { public: bool placeWordInCrossword ( vector < vector < char >>& board , string word ) { int m = board . size (), n = board [ 0 ]. size (); int k = word . size (); auto check = [ & ]( int i , int j , int a , int b ) { int x = i + a * k , y = j + b * k ; if ( x >= 0 && x < m && y >= 0 && y < n && board [ x ][ y ] != '#' ) { return false ; } for ( char & c : word ) { if ( i < 0 || i >= m || j < 0 || j >= n || ( board [ i ][ j ] != ' ' && board [ i ][ j ] != c )) { return false ; } i += a ; j += b ; } return true ; }; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { bool leftToRight = ( j == 0 || board [ i ][ j - 1 ] == '#' ) && check ( i , j , 0 , 1 ); bool rightToLeft = ( j == n - 1 || board [ i ][ j + 1 ] == '#' ) && check ( i , j , 0 , - 1 ); bool upToDown = ( i == 0 || board [ i - 1 ][ j ] == '#' ) && check ( i , j , 1 , 0 ); bool downToUp = ( i == m - 1 || board [ i + 1 ][ j ] == '#' ) && check ( i , j , - 1 , 0 ); if ( leftToRight || rightToLeft || upToDown || downToUp ) { return true ; } } } return false ; } };
```

### Python

```python
class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool: def check(i, j, a, b): x, y = i + a * k, j + b * k if 0 <= x < m and 0 <= y < n and board[x][y] != '#': return False for c in word: if (i < 0 or i >= m or j < 0 or j >= n or (board[i][j] != ' ' and board[i][j] != c)): return False i, j = i + a, j + b return True m, n = len(board), len(board[0]) k = len(word) for i in range(m): for j in range(n): left_to_right = (j == 0 or board[i][j - 1] == '#') and check(i, j, 0, 1) right_to_left = (j == n - 1 or board[i][j + 1] == '#') and check(i, j, 0, - 1) up_to_down = (i == 0 or board[i - 1][j] == '#') and check(i, j, 1, 0) down_to_up = (i == m - 1 or board[i + 1][j] == '#') and check(i, j, - 1, 0) if left_to_right or right_to_left or up_to_down or down_to_up: return True return False

```