Check if word can be placed in crossword

Array Matrix Enumeration

50.7% acceptance

Feb 25, 2026

328

311

You are given an m x n matrix board representing 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 or vertically if it doesn't occupy a '#' cell, each letter placed matches the cell or is empty, and there are no adjacent empty/letter cells beyond the word boundaries. Return true if word can be placed in board.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

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 w: Vec<char> = word.chars().collect();
    let wlen = w.len();
    
    // Check horizontal placements
    for r in 0..m {
      let mut c = 0;
      while c < n {
        if board[r][c] == '#' { c += 1; continue; }
        // Find segment start
        let start = c;
        while c < n && board[r][c] != '#' { c += 1; }
        let end = c; // exclusive
        let seg_len = end - start;
        if seg_len == wlen {
          // Check forward
          if check_word(&board[r][start..end], &w) { return true; }
          // Check backward
          let rev: Vec<char> = w.iter().copied().rev().collect();
          if check_word(&board[r][start..end], &rev) { return true; }
        }
      }
    }
    
    // Check vertical placements
    for c in 0..n {
      let mut r = 0;
      while r < m {
        if board[r][c] == '#' { r += 1; continue; }
        let start = r;
        while r < m && board[r][c] != '#' { r += 1; }
        let end = r;
        let seg_len = end - start;
        if seg_len == wlen {
          let col: Vec<char> = (start..end).map(|i| board[i][c]).collect();
          if check_word(&col, &w) { return true; }
          let rev: Vec<char> = w.iter().copied().rev().collect();
          if check_word(&col, &rev) { return true; }
        }
      }
    }
    false
  }
}

fn check_word(seg: &[char], word: &[char]) -> bool {
  seg.iter().zip(word.iter()).all(|(&s, &w)| s == ' ' || s == w)
}