Leetcode 2018: Check if Word Can Be Placed In Crossword
You are given an m x n matrix representing a crossword puzzle. The matrix contains lowercase English letters, empty spaces (’ ‘), and blocked cells (’#’). Given a word, determine if it can be placed horizontally or vertically in the crossword while adhering to the following constraints.
Problem
Approach
Steps
Complexity
Input: The input consists of a matrix board of size m x n, where each element is either a lowercase letter, an empty space (' '), or a blocked cell ('#'). A string word is also provided, representing the word that needs to be placed on the board.
Example: [['#', ' ', '#'], [' ', ' ', '#'], ['#', 'c', ' ']]
Constraints:
• m == board.length
• n == board[i].length
• 1 <= m * n <= 2 * 10^5
• board[i][j] will be ' ', '#', or a lowercase English letter.
• 1 <= word.length <= max(m, n)
Output: Return true if the word can be placed on the board, otherwise return false.
Example: true
Constraints:
• The output will be a boolean value indicating whether the word can be placed on the board.
Goal: The goal is to check if the word can be placed horizontally or vertically on the crossword puzzle, considering all given constraints.
Steps:
• For each row and column, check if the word fits in either direction (horizontal or vertical) with the given constraints.
• Ensure that the word does not overlap any blocked cells.
• Verify that there are no conflicting adjacent cells before and after placing the word.
Goal: The matrix board contains only lowercase letters, spaces, and blocked cells. The word must fit within the constraints of the board dimensions.
Steps:
• board[i][j] will be either a lowercase letter, ' ', or '#'.
• 1 <= m * n <= 2 * 10^5
• 1 <= word.length <= max(m, n)
Assumptions:
• The word can be placed horizontally or vertically.
• The grid is a crossword puzzle containing blocked cells, empty spaces, and already placed words.
• Input: [['#', ' ', '#'], [' ', ' ', '#'], ['#', 'c', ' ']]
• Explanation: The word 'abc' can be placed vertically starting at (0, 1) without conflicting with other letters or blocked cells.
• Input: [[' ', '#', 'a'], [' ', '#', 'c'], [' ', '#', 'a']]
• Explanation: It is impossible to place the word 'ac' because of the blocked cells and no available continuous empty space.
• Input: [['#', ' ', '#'], [' ', ' ', '#'], ['#', ' ', 'c']]
• Explanation: The word 'ca' can be placed horizontally from right to left in the third row.
Approach: The approach is to iterate over each possible starting position in the matrix and check if the word can be placed both horizontally and vertically at that position while satisfying all constraints.
Observations:
• We need to check both horizontal and vertical placements of the word at each valid position in the matrix.
• We can break down the problem by checking whether the word fits and adheres to the constraints at each possible position.
Steps:
• Check each row for possible horizontal placements.
• Check each column for possible vertical placements.
• For both placements, ensure the word fits and adheres to the constraints (e.g., no blocking cells and adjacent empty cells).
Empty Inputs:
• Ensure the solution handles cases where the board has empty cells but is large in size.
Large Inputs:
• Ensure the solution works efficiently for large boards with up to 2 * 10^5 cells.
Special Values:
• Handle cases where the word is longer than the board dimensions (m or n).
Constraints:
• Handle grids with only blocked cells or only empty cells.
bool same(vector<char> &row, int start, int end, string &s) {
if(end - start + 1 != s.size()) return false;
int i = 0, n = s.size();
while(i < n && (row[start + i] == ' ' || row[start + i] == s[i])) {
i++;
}
if(i == n) return true;
i = 0;
while(i < n && (row[end - i] == ' ' || row[end - i] == s[i]))
i++;
if(i == n) return true;
return false;
}
bool match(vector<vector<char>> &mtx, string &word) {
int n = mtx[0].size();
for(auto &row: mtx) {
for(int i = 0; i < n; ) {
int start;
while(i < n && row[i] == '#') i++;
start = i;
while(i < n && row[i] != '#') i++;
if(same(row, start, i - 1, word))
return true;
}
}
return false;
}
bool placeWordInCrossword(vector<vector<char>>& board, string word) {
int m = board.size(), n = board[0].size();
vector<vector<char>> trns(n, vector<char>(m));
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
trns[j][i] = board[i][j];
return match(trns, word) || match(board, word);
}
1 : Function Definition
bool same(vector<char> &row, int start, int end, string &s) {
This defines the function `same`, which checks if a substring in the `row` matches the given string `s` with allowance for spaces.
2 : Condition Check
if(end - start + 1 != s.size()) return false;
This checks if the length of the substring from `start` to `end` is equal to the size of the string `s`. If not, it returns false.
3 : Variable Initialization
int i = 0, n = s.size();
This initializes the loop counter `i` and stores the size of the string `s` in `n`.
4 : Loop for Matching from Start
while(i < n && (row[start + i] == ' ' || row[start + i] == s[i])) {
This starts a loop that checks if each character in the substring starting from `start` matches the corresponding character in `s`, allowing for spaces.
5 : Increment Counter
i++;
This increments the counter `i` to check the next character in the string and the row.
6 : Matching Check
if(i == n) return true;
If the entire string `s` has been matched, this returns true.
7 : Reset Loop Counter
i = 0;
This resets the counter `i` to start the second matching attempt from the end of the substring.
8 : Loop for Matching from End
while(i < n && (row[end - i] == ' ' || row[end - i] == s[i]))
This starts a loop that checks if each character in the substring from `end` matches the corresponding character in `s`, allowing for spaces.
9 : Increment Counter
i++;
This increments the counter `i` to check the next character in the row and the string.
10 : Matching Check
if(i == n) return true;
If the entire string `s` is matched in the reverse direction, this returns true.
11 : Return Statement
return false;
If neither the forward nor reverse match succeeds, it returns false.
12 : Function Definition
bool match(vector<vector<char>> &mtx, string &word) {
This defines the function `match`, which checks whether a word can be placed on the given 2D matrix (either horizontally or vertically).
13 : Grid Size Calculation
int n = mtx[0].size();
This calculates the number of columns in the matrix `mtx`, which will be used as the upper bound for column-wise iteration.
14 : Matrix Iteration
for(auto &row: mtx) {
This iterates over each row of the matrix `mtx`.
15 : Column Iteration
for(int i = 0; i < n; ) {
This iterates through the columns in the row.
16 : Start of Substring
int start;
This declares a variable `start` to store the starting index of the substring in the row.
17 : Skip '#' Characters
while(i < n && row[i] == '#') i++;
This skips any `#` characters in the row.
18 : Record Start Position
start = i;
This sets `start` to the current index `i` where the word could potentially start.
19 : Skip Non- '#' Characters
while(i < n && row[i] != '#') i++;
This skips any non-`#` characters in the row, as they mark the end of a potential word placement.
20 : Match Check
if(same(row, start, i - 1, word))
This calls the `same` function to check if the substring from `start` to `i-1` matches the given word.
21 : Return Result
return true;
If a match is found, it immediately returns `true`.
22 : Return Statement
return false;
If no match is found after processing all rows, it returns `false`.
23 : Main Function
bool placeWordInCrossword(vector<vector<char>>& board, string word) {
This defines the main function `placeWordInCrossword`, which calls the `match` function for both the original and transposed board.
24 : Matrix Transposition
vector<vector<char>> trns(n, vector<char>(m));
This initializes a transposed version of the matrix `board`.
25 : Transpose Logic
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
trns[j][i] = board[i][j];
This transposes the matrix `board` to facilitate checking column-wise word placements.
26 : Final Match Check
return match(trns, word) || match(board, word);
This checks if the word can be placed in either the transposed or original matrix.
Best Case: O(m * n)
Average Case: O(m * n)
Worst Case: O(m * n)
Description: We need to check each cell in the board for possible placements of the word.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant as we only need a few variables to track the word placements and their validity.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus