A Word in a Crossword Slot

Medium

You are given a crossword grid board of size m × n. Each cell is a space ' ' (empty), '#' (blocked) or a lowercase English letter (part of a word already filled in). The word word can be written horizontally (left to right or right to left) or vertically (top to bottom or bottom to top) if: - it does not cover any '#' cell; - each of its letters lands either on an empty cell or on a cell already holding that same letter; - right before its first letter and right after its last letter (along its direction) there is a '#' or the edge of the grid, so the word fills the whole slot. Return true if word can be written in, and false otherwise.

Example 1

board=[["#", " ", " "], ["#", "o", "#"], [" ", "g", " "]], word="dog" → True

The middle column runs the full height: "d" fills the empty cell, while "o" and "g" match the letters already there.

Example 2

board=[[" ", " ", " "], ["#", "#", "#"]], word="go" → False

The only horizontal slot is the whole top row of length 3, but the word has length 2, so an empty cell would touch it. Each column slot is just one cell long.

Example 3

board=[["t", " ", "#"], ["#", "#", "#"]], word="at" → True

The word may run right to left: "a" goes into the empty cell and "t" matches the letter already there.

Constraints

1 ≤ m · n ≤ 2 · 10⁵
Each cell is ' ', '#' or a lowercase English letter
1 ≤ len(word) ≤ max(m, n)
word consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Enumeration Matrix