Check if Word Can Be Placed In Crossword

Check if Word Can Be Placed In Crossword is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Word Search / Path Finding in Grid subpattern.

Problem statement

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:

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

Example 2:

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:

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.

Topics and companies

Topics: Array, Matrix, Enumeration.

How to practise Check if Word Can Be Placed In Crossword on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n * L), where m and n are the board dimensions and L is the length of the word. For each row and column, we scan for all possible segments, and for each segment of length L, we check each character. time and O(max(m, n)), for temporary storage of a column vector when checking columns. No extra space proportional to the board size is used. space.

Open Check if Word Can Be Placed In Crossword in the code editor, or read the Check if Word Can Be Placed In Crossword editorial for a worked solution with its approach and complexity analysis.

Where Check if Word Can Be Placed In Crossword sits in the DSA pattern sheet

Problems related to Check if Word Can Be Placed In Crossword

Other problems that use the same Word Search / Path Finding in Grid and Backtracking Patterns techniques:

Preparing this workspace.