2018. Check if Word Can Be Placed In Crossword
Problem Description
This problem involves a matrix representing a crossword puzzle, which includes lowercase English letters, spaces (represented by ' ') for empty cells, and the '#' character for blocked cells. The goal is to determine if a given word can be placed in the puzzle following certain conditions. The word can be placed either horizontally or vertically and must adhere to the following rules:
- The word cannot be placed in cells that contain the
'#'character (blocked cells). - Each letter of the word must either fill an empty cell (designated by spaces
' ') or match an existing letter on the board. - If the word is placed horizontally, there should not be any empty cells or other letters immediately to the left or right of the word.
- If the word is placed vertically, there should not be any empty cells or other letters immediately above or below the word.
The task is to return true if the word can be placed on the board according to the rules, or false otherwise.
Intuition
To decide whether the given word can be positioned within the board, we should check each cell of the matrix where the first letter of the word could potentially be placed. This checking has to take into account the orientation (horizontal and vertical) and also the direction (from left to right, right to left, top to bottom, and bottom to top).
The intuition behind the provided solution is to systematically iterate over every cell in the matrix and try to match the word considering all possible starting positions and directions that adhere to the crossword rules. For every potential starting position, we examine whether the word would fit without violating any constraints such as running into blocked cells or mismatching existing letters. This involves:
- Checking horizontally to the right (left_to_right) and to the left (right_to_left).
- Checking vertically downwards (up_to_down) and upwards (down_to_up).
If any of these checks succeed, indicating that the word fits without issue, the function will return true. If no such fitting place is found across the entire board, the function will return false.
The solution efficiently prunes the search by ensuring the word's placement does not start or end next to an empty cell or a different letter when placing words horizontally or vertically. As such, it starts the placement from the border of the board or next to a blocked cell and checks if every letter of the word can be placed in a suitable position.
Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?
Solution Approach
The solution uses a nested loop to iterate through every cell in the board. For each cell, it checks if this cell could be a potential starting point for the word by following these steps:
- It checks if the current cell and its immediate neighbor in the opposite direction of the check are either on the edge of the board or blocked by a
'#'. This ensures that we only start at valid positions according to the rules of the puzzle. - If the starting position is valid, it then invokes the
checkfunction which will attempt to place the word starting from that position, moving either horizontally or vertically and either forwards or backwards depending on the check being performed.
The check function is designed to validate the placement of the word by iterating over each letter of the word and checking the following conditions:
- The current position is within the bounds of the board.
- The current board cell is not blocked (i.e., not
'#'). - The current board cell is either empty (i.e.,
' ') or matches the corresponding letter in the word.
The check function also ensures that the letter after the last one of the word (calculated by x, y = i + a * k, j + b * k) is either out of bounds or blocked. This ensures that the word does not end next to a cell that could violate the horizontal or vertical placement rules.
The data structures used in the solution are:
- The
boardmatrix which stores the characters as a 2D list. - Variables
mandnwhich represent the number of rows and columns in theboard, respectively. - Variable
kwhich is the length of theword.
The solution approach does not use any additional complex algorithms or patterns. It simply leverages careful iteration and checking of board states to determine if the word can be placed.
Here's a code snippet encapsulating that logic:
1for i in range(m):
2 for j in range(n):
3 left_to_right = (j == 0 or board[i][j - 1] == '#') and check(i, j, 0, 1)
4 right_to_left = (j == n - 1 or board[i][j + 1] == '#') and check(i, j, 0, -1)
5 up_to_down = (i == 0 or board[i - 1][j] == '#') and check(i, j, 1, 0)
6 down_to_up = (i == m - 1 or board[i + 1][j] == '#') and check(i, j, -1, 0)
7 if left_to_right or right_to_left or up_to_down or down_to_up:
8 return True
9return False
The and operator in left_to_right, right_to_left, up_to_down, and down_to_up checks combines the start position validation and the check function call. If any of these conditions return True, it means the word can be placed in the board following the puzzle rules.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Example Walkthrough
Consider a 3 x 3 crossword puzzle board and the word "cat":
1board = [ 2 ['#', 'c', '#'], 3 [' ', 'a', ' '], 4 ['#', 't', '#'] 5]
We want to check if we can place the word "cat" on this board.
Using our solution approach, we will check each cell starting from (0,0) to (2,2) to find a valid placement for "cat".
First, we check horizontally to the right (left_to_right). Starting from (0,0) we find it's a blocked cell ('#'), so we move to (0,1). The cell (0,1) contains the first letter of the word "cat", 'c', and cell (0,0) is blocked, which is a valid start position. However, we cannot place "cat" horizontally to the right because there is no space to fit the entire word "cat".
Next, we check horizontally to the left (right_to_left). This direction is not applicable in this case as we are looking for starting positions.
Then, we check vertically downwards (up_to_down). From (0,1), we realize (0,0) is blocked, providing a potential starting position for "cat". We can successfully match 'c' with 'c', then move to the next cell (1,1) and match 'a' with 'a', and finally move to (2,1) and see that 't' can match 't'. Thus, "cat" can be placed vertically from (0,1) to (2,1).
Since we found a valid placement for "cat", we do not need to check vertically upwards (down_to_up) from (0,1). The check function would return true, and the algorithm would confirm that "cat" can be placed on the board.
So in our algorithm, as soon as it runs the up_to_down check starting at (0,1), it will return true, indicating that the word "cat" can indeed be placed on the board vertically. The result is obtained without having to check other cells or directions, as the solution is efficiently designed to stop once a valid position is found.
Solution Implementation
1from typing import List
2
3class Solution:
4 def place_word_in_crossword(self, board: List[List[str]], word: str) -> bool:
5 # Function to check if the word fits starting from position (i, j) in the direction specified by (delta_i, delta_j)
6 def is_valid_placement(i, j, delta_i, delta_j):
7 # Move to the end of the word in the specified direction to check if it is within bounds or blocked by '#'
8 end_i, end_j = i + delta_i * word_length, j + delta_j * word_length
9 if not (0 <= end_i < rows and 0 <= end_j < cols) or (board[end_i][end_j] == '#'):
10 return False
11
12 # Iterate through each character of the 'word' to check for a valid placement
13 for char in word:
14 # Check for out of bounds or if the current board cell is blocked or does not match the word character
15 if (
16 i < 0 or i >= rows or
17 j < 0 or j >= cols or
18 (board[i][j] != ' ' and board[i][j] != char)
19 ):
20 return False
21
22 # Move to the next cell in the specified direction
23 i, j = i + delta_i, j + delta_j
24
25 return True
26
27 rows, cols = len(board), len(board[0]) # Get the dimensions of the board
28 word_length = len(word) # Get the length of the word
29
30 # Iterate over every cell in the board
31 for i in range(rows):
32 for j in range(cols):
33 # Check all four directions from the current cell: left to right, right to left, top to bottom, bottom to top
34 left_to_right = (j == 0 or board[i][j - 1] == '#') and is_valid_placement(i, j, 0, 1)
35 right_to_left = (j == cols - 1 or board[i][j + 1] == '#') and is_valid_placement(i, j, 0, -1)
36 top_to_bottom = (i == 0 or board[i - 1][j] == '#') and is_valid_placement(i, j, 1, 0)
37 bottom_to_top = (i == rows - 1 or board[i + 1][j] == '#') and is_valid_placement(i, j, -1, 0)
38
39 # If the word can be placed in any direction, return True
40 if left_to_right or right_to_left or top_to_bottom or bottom_to_top:
41 return True
42
43 # If no valid placement is found, return False
44 return False
45
46# Example usage:
47# solution = Solution()
48# result = solution.place_word_in_crossword(board=[['#',' ','#'],[' ',' ','#'],['#','c',' ']], word="abc")
49# print(result) # Output will be True or False based on if the word can be placed on the board
501class Solution {
2 private int rows;
3 private int cols;
4 private char[][] board;
5 private String word;
6 private int wordLength;
7
8 // Method to check if the word can be placed in the crossword
9 public boolean placeWordInCrossword(char[][] board, String word) {
10 rows = board.length;
11 cols = board[0].length;
12 this.board = board;
13 this.word = word;
14 wordLength = word.length();
15
16 // Traverse the board to check every potential starting point
17 for (int i = 0; i < rows; ++i) {
18 for (int j = 0; j < cols; ++j) {
19 // Check four possible directions from the current cell
20 // Left to right
21 boolean leftToRight = (j == 0 || board[i][j - 1] == '#') && canPlaceWord(i, j, 0, 1);
22 // Right to left
23 boolean rightToLeft = (j == cols - 1 || board[i][j + 1] == '#') && canPlaceWord(i, j, 0, -1);
24 // Up to down
25 boolean upToDown = (i == 0 || board[i - 1][j] == '#') && canPlaceWord(i, j, 1, 0);
26 // Down to up
27 boolean downToUp = (i == rows - 1 || board[i + 1][j] == '#') && canPlaceWord(i, j, -1, 0);
28
29 // If any direction is possible, return true
30 if (leftToRight || rightToLeft || upToDown || downToUp) {
31 return true;
32 }
33 }
34 }
35 // If no direction is possible, return false
36 return false;
37 }
38
39 // Helper method to check if the word can be placed starting from (i, j) in the specified direction (a, b)
40 private boolean canPlaceWord(int i, int j, int rowIncrement, int colIncrement) {
41 int endRow = i + rowIncrement * wordLength;
42 int endCol = j + colIncrement * wordLength;
43
44 // Check if the word goes out of bounds or is not terminated properly
45 if (endRow < 0 || endRow >= rows || endCol < 0 || endCol >= cols || board[endRow][endCol] != '#') {
46 return false;
47 }
48
49 // Check each character to see if the word fits
50 for (int p = 0; p < wordLength; ++p) {
51 if (i < 0 || i >= rows || j < 0 || j >= cols
52 || (board[i][j] != ' ' && board[i][j] != word.charAt(p))) {
53 return false;
54 }
55 i += rowIncrement;
56 j += colIncrement;
57 }
58 return true;
59 }
60}
611class Solution {
2public:
3 // Function to determine if a word can be placed in a crossword
4 bool placeWordInCrossword(vector<vector<char>>& board, string word) {
5 int numRows = board.size(), numCols = board[0].size(); // board dimensions
6 int wordLen = word.size(); // length of the word to be placed
7
8 // Lambda function to check if the word fits in the given direction
9 auto check = [&](int row, int col, int deltaRow, int deltaCol) {
10 int endRow = row + deltaRow * wordLen, endCol = col + deltaCol * wordLen;
11 // Check if the end position is not blocked by '#'
12 if (endRow >= 0 && endRow < numRows && endCol >= 0 && endCol < numCols && board[endRow][endCol] != '#') {
13 return false;
14 }
15 // Iterate over each character in the word
16 for (char& c : word) {
17 // Check boundaries and match the character with the board or wildcard
18 if (row < 0 || row >= numRows || col < 0 || col >= numCols || (board[row][col] != ' ' && board[row][col] != c)) {
19 return false;
20 }
21 row += deltaRow;
22 col += deltaCol;
23 }
24 return true;
25 };
26
27 // Iterate over each cell in the board
28 for (int i = 0; i < numRows; ++i) {
29 for (int j = 0; j < numCols; ++j) {
30 // Check four possible directions where the word can be placed
31 bool leftToRight = (j == 0 || board[i][j - 1] == '#') && check(i, j, 0, 1);
32 bool rightToLeft = (j == numCols - 1 || board[i][j + 1] == '#') && check(i, j, 0, -1);
33 bool upToDown = (i == 0 || board[i - 1][j] == '#') && check(i, j, 1, 0);
34 bool downToUp = (i == numRows - 1 || board[i + 1][j] == '#') && check(i, j, -1, 0);
35
36 // If the word can be placed in any direction, return true
37 if (leftToRight || rightToLeft || upToDown || downToUp) {
38 return true;
39 }
40 }
41 }
42 // Return false if the word can't be placed on the board in any direction
43 return false;
44 }
45};
461// Function to check if a word can be placed in a crossword
2function placeWordInCrossword(board: char[][], word: string): boolean {
3 const numRows = board.length; // Number of rows in the board
4 const numCols = board[0].length; // Number of columns in the board
5 const wordLen = word.length; // Length of the word to be placed
6
7 // Helper function to check if the word fits in the given direction
8 const check = (row: number, col: number, deltaRow: number, deltaCol: number): boolean => {
9 const endRow = row + deltaRow * wordLen;
10 const endCol = col + deltaCol * wordLen;
11 // Check if the end position is outside the boundary or blocked by '#'
12 if (endRow >= 0 && endRow <= numRows && endCol >= 0 && endCol <= numCols && (board[endRow] === undefined || board[endRow][endCol] !== '#')) {
13 // Iterate over each character in the word
14 for (let index = 0; index < wordLen; ++index) {
15 const char = word[index];
16 // Check boundaries and match the character with the board or wildcard
17 if (row < 0 || row >= numRows || col < 0 || col >= numCols || (board[row][col] !== ' ' && board[row][col] !== char)) {
18 return false;
19 }
20 row += deltaRow;
21 col += deltaCol;
22 }
23 return true;
24 }
25 return false;
26 };
27
28 // Iterate over each cell in the board
29 for (let i = 0; i < numRows; ++i) {
30 for (let j = 0; j < numCols; ++j) {
31 // Check four possible directions where the word can be placed
32 const leftToRight = (j === 0 || board[i][j - 1] === '#') && check(i, j, 0, 1);
33 const rightToLeft = (j === numCols - 1 || board[i][j + 1] === '#') && check(i, j, 0, -1);
34 const upToDown = (i === 0 || board[i - 1][undefined] === '#' || board[i - 1][j] === '#') && check(i, j, 1, 0);
35 const downToUp = (i === numRows - 1 || board[i + 1] === undefined || board[i + 1][j] === '#') && check(i, j, -1, 0);
36
37 // If the word can be placed in any direction, return true
38 if (leftToRight || rightToLeft || upToDown || downToUp) {
39 return true;
40 }
41 }
42 }
43 // Return false if the word can't be placed on the board in any direction
44 return false;
45}
46Depth first search is equivalent to which of the tree traversal order?
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(m * n * k), where m is the number of rows in the board, n is the number of columns in the board, and k is the length of the word to be placed. This complexity arises because the code iterates over all cells of the board (m * n) and for each cell, it attempts to place the word in all four directions. The check function, which is called for each direction, runs a loop up to the length of the word (k).
Additionally, when evaluating the board for possible placements, the algorithm checks the perpendicular cells to ensure placement is at the beginning or end of a word sequence (which is a constant time check). Due to these operations being constant in time, they do not impact the linear relationship between the time complexity and the number of cells times the length of the word.
Space Complexity
The space complexity of the code is O(1) (constant space complexity). This is because the algorithm only uses a fixed amount of extra space for variables that store the dimensions of the board and indices during the checks regardless of the input size. No additional space proportional to the input size is required beyond what is used to store the board and word, which are inputs and not counted towards the space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following is a good use case for backtracking?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.