Introduction

In this blog post, we will explore how to solve the LeetCode problem "2018" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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.

Explanation

• Iterate and Check: Iterate through the board to find potential starting positions for the word. For each potential start, check if the word can be placed horizontally or vertically (both forward and backward).
  • Validity Check: When attempting to place a word, ensure that each cell is either empty (' ') or matches the corresponding letter in the word. Also, ensure that the placement does not violate the adjacency rule (no spaces or letters directly beside or above/below).
  • Early Exit: Return True as soon as a valid placement is found. If the loop completes without finding a valid placement, return False.

• Runtime Complexity: O(m n word.length), where m and n are the dimensions of the board. Storage Complexity: O(1).

Code

    def placeWordInCrossword(board, word):
    m = len(board)
    n = len(board[0])
    word_len = len(word)

    def check_horizontal(row, col, forward):
        if forward:
            if col + word_len > n:
                return False
            if col > 0 and board[row][col - 1] != '#':
                return False
            if col + word_len < n and board[row][col + word_len] != '#':
                return False
            for i in range(word_len):
                if board[row][col + i] != ' ' and board[row][col + i] != word[i]:
                    return False
            return True
        else:
            if col - word_len + 1 < 0:
                return False
            if col < n - 1 and board[row][col + 1] != '#':
                return False
            if col - word_len >= 0 and board[row][col - word_len] != '#':
                return False

            for i in range(word_len):
                if board[row][col - i] != ' ' and board[row][col - i] != word[i]:
                    return False
            return True

    def check_vertical(row, col, forward):
        if forward:
            if row + word_len > m:
                return False
            if row > 0 and board[row - 1][col] != '#':
                return False
            if row + word_len < m and board[row + word_len][col] != '#':
                return False

            for i in range(word_len):
                if board[row + i][col] != ' ' and board[row + i][col] != word[i]:
                    return False
            return True
        else:
            if row - word_len + 1 < 0:
                return False
            if row < m - 1 and board[row + 1][col] != '#':
                return False
            if row - word_len >= 0 and board[row - word_len][col] != '#':
                return False

            for i in range(word_len):
                if board[row - i][col] != ' ' and board[row - i][col] != word[i]:
                    return False
            return True

    for i in range(m):
        for j in range(n):
            if board[i][j] == ' ' or board[i][j] == word[0]:
                if check_horizontal(i, j, True):
                    return True
                if check_horizontal(i, j + word_len -1, False):

                    return True

            if board[i][j] == ' ' or board[i][j] == word[0]:

                if check_vertical(i, j, True):
                    return True
                if check_vertical(i + word_len -1, j, False):
                    return True

    return False