How hard is LeetCode 2018. Check if Word Can Be Placed In Crossword?

LeetCode 2018. Check if Word Can Be Placed In Crossword is rated Medium on LeetCode.

What is the time complexity of LeetCode 2018. Check if Word Can Be Placed In Crossword?

The Python solution on this page runs in O(m \times n).

What is the space complexity of LeetCode 2018. Check if Word Can Be Placed In Crossword?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2018. Check if Word Can Be Placed In Crossword cover?

LeetCode 2018. Check if Word Can Be Placed In Crossword is tagged Array, Enumeration and Matrix on LeetCode.

Check if Word Can Be Placed In Crossword — LeetCode 2018 Python Solution

MediumArrayEnumerationMatrix

Problem: #2018
Pattern: Matrix and Grid
Reading time: 6 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        def check(i, j, a, b):
            x, y = i + a * k, j + b * k
            if 0 <= x < m and 0 <= y < n and board[x][y] != '#':
                return False
            for c in word:
                if (
                    i < 0
                    or i >= m
                    or j < 0
                    or j >= n
                    or (board[i][j] != ' ' and board[i][j] != c)
                ):
                    return False
                i, j = i + a, j + b
            return True

        m, n = len(board), len(board[0])
        k = len(word)
        for i in range(m):
            for j in range(n):
                left_to_right = (j == 0 or board[i][j - 1] == '#') and check(i, j, 0, 1)
                right_to_left = (j == n - 1 or board[i][j + 1] == '#') and check(
                    i, j, 0, -1
                )
                up_to_down = (i == 0 or board[i - 1][j] == '#') and check(i, j, 1, 0)
                down_to_up = (i == m - 1 or board[i + 1][j] == '#') and check(
                    i, j, -1, 0
                )
                if left_to_right or right_to_left or up_to_down or down_to_up:
                    return True
        return False

Complexity

Measure	Complexity
Time	O(m \times n)
Space	O(1) auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 2018. Check if Word Can Be Placed In Crossword is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2018. Check if Word Can Be Placed In Crossword?: LeetCode 2018. Check if Word Can Be Placed In Crossword is rated Medium on LeetCode.
What is the time complexity of LeetCode 2018. Check if Word Can Be Placed In Crossword?: The Python solution on this page runs in O(m \times n).
What is the space complexity of LeetCode 2018. Check if Word Can Be Placed In Crossword?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2018. Check if Word Can Be Placed In Crossword cover?: LeetCode 2018. Check if Word Can Be Placed In Crossword is tagged Array, Enumeration and Matrix on LeetCode.