2018. Check if Word Can Be Placed In Crossword LeetCode Solution
In this guide, you will get 2018. Check if Word Can Be Placed In Crossword LeetCode Solution with the best time and space complexity. The solution to Check if Word Can Be Placed In Crossword problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Check if Word Can Be Placed In Crossword
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.
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
2018. Check if Word Can Be Placed In Crossword LeetCode Solution in C++
class Solution {
public:
bool placeWordInCrossword(vector<vector<char>>& board, string word) {
for (const vector<vector<char>>& state : {board, getRotated(board)})
for (const vector<char>& chars : state)
for (const string& token : getTokens(join(chars)))
for (const string& letters :
{word, string{word.rbegin(), word.rend()}})
if (letters.length() == token.length())
if (canFit(letters, token))
return true;
return false;
}
private:
vector<vector<char>> getRotated(const vector<vector<char>>& board) {
const int m = board.size();
const int n = board[0].size();
vector<vector<char>> rotated(n, vector<char>(m));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
rotated[j][i] = board[i][j];
return rotated;
}
vector<string> getTokens(const string& row) {
vector<string> tokens;
int start = 0;
int end;
string token;
do {
end = row.find('#', start);
token = row.substr(start, end - start);
if (!token.empty())
tokens.push_back(token);
start = end + 1;
} while (end != string::npos);
return tokens;
}
string join(const vector<char>& chars) {
string joined;
for (const char c : chars)
joined += c;
return joined;
}
bool canFit(const string& letters, const string& token) {
for (int i = 0; i < letters.length(); ++i)
if (token[i] != ' ' && token[i] != letters[i])
return false;
return true;
}
}; /* code provided by PROGIEZ */
2018. Check if Word Can Be Placed In Crossword LeetCode Solution in Java
class Solution {
public boolean placeWordInCrossword(char[][] board, String word) {
for (char[][] state : new char[][][] {board, getRotated(board)})
for (char[] chars : state)
for (final String token : String.valueOf(chars).split("#"))
for (final String letters :
new String[] {word, new StringBuilder(word).reverse().toString()})
if (letters.length() == token.length())
if (canFit(letters, token))
return true;
return false;
}
private char[][] getRotated(char[][] board) {
final int m = board.length;
final int n = board[0].length;
char[][] rotated = new char[n][m];
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
rotated[j][i] = board[i][j];
return rotated;
}
private boolean canFit(final String letters, final String token) {
for (int i = 0; i < letters.length(); ++i)
if (token.charAt(i) != ' ' && token.charAt(i) != letters.charAt(i))
return false;
return true;
}
} // code provided by PROGIEZ
2018. Check if Word Can Be Placed In Crossword LeetCode Solution in Python
class Solution:
def placeWordInCrossword(self, board: list[list[str]], word: str) -> bool:
for x in board, zip(*board):
for row in x:
for token in ''.join(row).split('#'):
for letters in word, word[::-1]:
if len(token) == len(letters):
if all(c in (' ', letter) for c, letter in zip(token, letters)):
return True
return False # code by PROGIEZ
