Problem

You are given an m x n matrix board, representing thecurrent 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 placedhorizontally (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 ifword can be placed inboard , orfalse otherwise.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

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

Solution

Method 1 – Scan and Check All Directions

Intuition

A word can be placed in the crossword if it fits in any row or column (in either direction) and matches the crossword rules. We can scan all rows and columns, and for each possible slot, check if the word (or its reverse) can be placed there.

Approach

  1. For each row and each column, extract all contiguous segments separated by ‘#’.
  2. For each segment of length equal to the word, check if the word or its reverse can be placed:
    • Each cell must be empty (’ ‘) or match the corresponding letter.
    • The segment must not be adjacent to a letter or empty cell (i.e., must be bounded by ‘#’ or the edge).
  3. If any such placement is possible, return true.
  4. If no placement is possible, return false.

Complexity

  • ⏰ Time complexity: O(mn * l), where m, n are the board dimensions and l is the word length.
  • 🧺 Space complexity: O(1)
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size(), l = word.size();
        auto check = [&](vector<char>& seg, string w) {
            if (seg.size() != w.size()) return false;
            for (int i = 0; i < w.size(); ++i)
                if (seg[i] != ' ' && seg[i] != w[i]) return false;
            return true;
        };
        for (int i = 0; i < m; ++i) {
            for (int dir = 0; dir < 2; ++dir) {
                vector<char> row = board[i];
                if (dir) reverse(row.begin(), row.end());
                for (int j = 0; j <= n - l; ++j) {
                    if ((j == 0 || row[j-1] == '#') && (j + l == n || row[j+l] == '#')) {
                        vector<char> seg(row.begin() + j, row.begin() + j + l);
                        if (check(seg, word)) return true;
                    }
                }
            }
        }
        for (int j = 0; j < n; ++j) {
            for (int dir = 0; dir < 2; ++dir) {
                vector<char> col(m);
                for (int i = 0; i < m; ++i) col[i] = board[i][j];
                if (dir) reverse(col.begin(), col.end());
                for (int i = 0; i <= m - l; ++i) {
                    if ((i == 0 || col[i-1] == '#') && (i + l == m || col[i+l] == '#')) {
                        vector<char> seg(col.begin() + i, col.begin() + i + l);
                        if (check(seg, word)) return true;
                    }
                }
            }
        }
        return false;
    }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func placeWordInCrossword(board [][]byte, word string) bool {
    m, n, l := len(board), len(board[0]), len(word)
    check := func(seg []byte, w string) bool {
        if len(seg) != len(w) { return false }
        for i := range w {
            if seg[i] != ' ' && seg[i] != w[i] { return false }
        }
        return true
    }
    for i := 0; i < m; i++ {
        for d := 0; d < 2; d++ {
            row := make([]byte, n)
            for j := 0; j < n; j++ { row[j] = board[i][j] }
            if d == 1 {
                for j := 0; j < n/2; j++ { row[j], row[n-1-j] = row[n-1-j], row[j] }
            }
            for j := 0; j <= n-l; j++ {
                if (j == 0 || row[j-1] == '#') && (j+l == n || row[j+l] == '#') {
                    if check(row[j:j+l], word) { return true }
                }
            }
        }
    }
    for j := 0; j < n; j++ {
        for d := 0; d < 2; d++ {
            col := make([]byte, m)
            for i := 0; i < m; i++ { col[i] = board[i][j] }
            if d == 1 {
                for i := 0; i < m/2; i++ { col[i], col[m-1-i] = col[m-1-i], col[i] }
            }
            for i := 0; i <= m-l; i++ {
                if (i == 0 || col[i-1] == '#') && (i+l == m || col[i+l] == '#') {
                    if check(col[i:i+l], word) { return true }
                }
            }
        }
    }
    return false
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    public boolean placeWordInCrossword(char[][] board, String word) {
        int m = board.length, n = board[0].length, l = word.length();
        for (int i = 0; i < m; ++i) {
            for (int d = 0; d < 2; ++d) {
                char[] row = board[i].clone();
                if (d == 1) reverse(row);
                for (int j = 0; j <= n - l; ++j) {
                    if ((j == 0 || row[j-1] == '#') && (j + l == n || row[j+l] == '#')) {
                        if (check(row, j, word)) return true;
                    }
                }
            }
        }
        for (int j = 0; j < n; ++j) {
            for (int d = 0; d < 2; ++d) {
                char[] col = new char[m];
                for (int i = 0; i < m; ++i) col[i] = board[i][j];
                if (d == 1) reverse(col);
                for (int i = 0; i <= m - l; ++i) {
                    if ((i == 0 || col[i-1] == '#') && (i + l == m || col[i+l] == '#')) {
                        if (check(col, i, word)) return true;
                    }
                }
            }
        }
        return false;
    }
    private boolean check(char[] arr, int start, String word) {
        for (int i = 0; i < word.length(); ++i)
            if (arr[start + i] != ' ' && arr[start + i] != word.charAt(i)) return false;
        return true;
    }
    private void reverse(char[] arr) {
        for (int i = 0, j = arr.length - 1; i < j; ++i, --j) {
            char t = arr[i]; arr[i] = arr[j]; arr[j] = t;
        }
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    fun placeWordInCrossword(board: Array<CharArray>, word: String): Boolean {
        val m = board.size; val n = board[0].size; val l = word.length
        fun check(arr: CharArray, start: Int, w: String): Boolean {
            for (i in w.indices) if (arr[start + i] != ' ' && arr[start + i] != w[i]) return false
            return true
        }
        fun reverse(arr: CharArray) { var i = 0; var j = arr.size - 1; while (i < j) { val t = arr[i]; arr[i] = arr[j]; arr[j] = t; i++; j-- } }
        for (i in 0 until m) {
            for (d in 0..1) {
                val row = board[i].clone()
                if (d == 1) reverse(row)
                for (j in 0..n-l) {
                    if ((j == 0 || row[j-1] == '#') && (j + l == n || row[j+l] == '#')) {
                        if (check(row, j, word)) return true
                    }
                }
            }
        }
        for (j in 0 until n) {
            for (d in 0..1) {
                val col = CharArray(m) { board[it][j] }
                if (d == 1) reverse(col)
                for (i in 0..m-l) {
                    if ((i == 0 || col[i-1] == '#') && (i + l == m || col[i+l] == '#')) {
                        if (check(col, i, word)) return true
                    }
                }
            }
        }
        return false
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def placeWordInCrossword(self, board: list[list[str]], word: str) -> bool:
        m, n, l = len(board), len(board[0]), len(word)
        def check(arr: list[str], w: str) -> bool:
            return all(a == ' ' or a == b for a, b in zip(arr, w))
        for rows in (board, list(zip(*board))):
            for row in rows:
                s = ''.join(row)
                for seg in s.split('#'):
                    if len(seg) == l:
                        if check(seg, word) or check(seg, word[::-1]):
                            return True
        return False
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn place_word_in_crossword(board: Vec<Vec<char>>, word: String) -> bool {
        let m = board.len();
        let n = board[0].len();
        let l = word.len();
        let check = |arr: &[char], w: &str| arr.len() == w.len() && arr.iter().zip(w.chars()).all(|(&a, b)| a == ' ' || a == b);
        for rows in [board.clone(), (0..n).map(|j| (0..m).map(|i| board[i][j]).collect()).collect()] {
            for row in rows {
                let s: String = row.iter().collect();
                for seg in s.split('#') {
                    if seg.len() == l {
                        let arr: Vec<char> = seg.chars().collect();
                        if check(&arr, &word) || check(&arr, &word.chars().rev().collect::<String>()) {
                            return true;
                        }
                    }
                }
            }
        }
        false
    }
}