Check if Word Can Be Placed In Crossword
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 theboard. - 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
+---+---+---+ | # | | # | | | | # | | # | c | | +---+---+---+
Input
board = [["#"," ","#"],[" "," ","#"],["#","c"," "]], word = "abc"Output
trueThe word "abc" can be placed vertically from top to bottom.
Example 2
+---+---+---+ | | # | a | | | # | c | | | # | a | +---+---+---+
Input
board = [[" ","#","a"],[" ","#","c"],[" ","#","a"]], word = "ac"Output
falseIt is impossible to place the word because there will always be a space or letter above or below it.
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.