Check if Word Can Be Placed In Crossword Interview Question for Google

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.

For example:

board = [['#', ' ', '#'], [' ', ' ', '#'], ['#', 'c', ' ']], word = "abc"

return true because the word "abc" can be placed as shown above (top to bottom).

As another example:

board = [[' ', '#', 'a'], [' ', '#', 'c'], [' ', '#', 'a']], word = "ac"

return false because it is impossible to place the word because there will always be a space/letter above or below it.

Naive Solution

The naive solution would involve iterating through every possible position and orientation (horizontal, vertical, reversed horizontal, reversed vertical) in the board and checking if the word can be placed there according to the problem's constraints.

Big O Runtime

O(m * n * len(word)), where m is the number of rows, n is the number of columns in the board, and len(word) is the length of the word to be placed. This is because, in the worst case, we might have to iterate through every cell in the board and for each cell, try to fit the word in all four possible orientations.

Big O Space

O(1). The naive solution has constant space complexity because we do not use any extra data structures that scale with the input size.

Optimal Solution

The optimal solution has the same time complexity as the naive solution, but improves readability and structure by using helper functions.

Algorithm

Iterate through the board to find possible starting positions for the word.
For each possible starting position, check if the word can be placed horizontally, vertically, reversed horizontally, or reversed vertically.
Return true if the word can be placed in any of the checked orientations, otherwise return false.

Edge Cases

Empty board.
Empty word.
Word longer than the board dimensions.
Word contains characters not in the board's alphabet.
Board contains invalid characters.

Code (Python)

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

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

        def check_vertical(row, col, direction):
            if direction == 1:
                if row + len(word) > m:
                    return False
                if row > 0 and board[row - 1][col] != '#':
                    return False
                if row + len(word) < m and board[row + len(word)][col] != '#':
                    return False
                for i in range(len(word)):
                    if board[row + i][col] != ' ' and board[row + i][col] != word[i]:
                        return False
                return True
            else:
                if row - len(word) + 1 < 0:
                    return False
                if row < m - 1 and board[row + 1][col] != '#':
                    return False
                if row - len(word) >= 0 and board[row - len(word)][col] != '#':
                    return False
                for i in range(len(word)):
                    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] != '#':
                    if check_horizontal(i, j, 1) and word == word[::-1]:
                        return True
                    if check_horizontal(i, j, -1) and word != word[::-1]:
                        return True
                    if check_vertical(i, j, 1) and word == word[::-1]:
                        return True
                    if check_vertical(i, j, -1) and word != word[::-1]:
                        return True

        return False

Big O Runtime

O(m * n * len(word)), where m is the number of rows, n is the number of columns in the board, and len(word) is the length of the word to be placed.

Big O Space

O(1). The solution has constant space complexity because we do not use any extra data structures that scale with the input size.