Editorial
Core insight
Check if Word Can Be Placed In Crossword · Backtracking Patterns
Core Insight for Check if Word Can Be Placed In Crossword
The key insight that simplifies LeetCode 2018 is to stop looking at individual cells and start looking at segments.
In a crossword, a valid slot for a word is determined strictly by # characters and the grid edges. A row like ['a', ' ', '#', ' ', ' ', ' '] contains two distinct segments:
"a "(length 2)" "(length 3)
Instead of asking "Can I start the word at ?", we ask "Does this segment match my word?"
This transforms the problem from a coordinate-based search into a stream processing problem. We extract all valid horizontal and vertical segments. For a segment to be a candidate, it must satisfy an invariant: The segment length must exactly equal the word length.
If the lengths match, we simply verify if the segment is compatible with word or reversed(word). Compatibility means that for every position , the segment character is either a space ' ' or identical to word[i].
Visual Description:
Imagine traversing a single row. You maintain a pointer at the start of a potential slot. As you iterate, you advance until you hit a #. This defines a segment. You check this segment against the word. Then, you move the start pointer past the # and repeat. This effectively "prunes" the search space to only valid structural slots, eliminating the need to check invalid starting positions.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 2018: Check if Word Can Be Placed In Crossword Solution & Explanation
Problem Overview
TL;DR: The optimal solution treats the grid as a collection of horizontal and vertical segments separated by blocked cells (#), checking if any segment matches the target word in length and character compatibility (forward or backward).
In LeetCode 2018, "Check if Word Can Be Placed In Crossword," you are provided with a grid representing a crossword puzzle state. The grid contains existing letters, empty spaces ( ), and blocked cells (#). Your task is to determine if a specific word can be placed into the grid according to strict crossword rules: the word must fit perfectly between obstacles (or grid boundaries) without overlapping blocked cells, and any existing letters in the chosen slot must match the corresponding letters in the word. The placement can be horizontal or vertical, and read either forward or backward.
Brute Force Approach for Check if Word Can Be Placed In Crossword
The naive approach attempts to simulate the placement of the word starting at every possible cell in the grid.
For every cell in the matrix, the algorithm:
- Attempts to place the
wordhorizontally (left-to-right). - Attempts to place the
wordhorizontally (right-to-left). - Attempts to place the
wordvertically (top-to-bottom). - Attempts to place the
wordvertically (bottom-to-top).
For each attempt, it checks:
- Does the word stay within grid boundaries?
- Does the word avoid all
#cells? - Do the characters match (or is the cell empty)?
- Crucially: Is the cell immediately before the start and immediately after the end either a
#or a grid boundary? (This ensures the word fits exactly).
Pseudo-code
function solve(board, word):
for r from 0 to m-1:
for c from 0 to n-1:
if check_placement(r, c, word, direction="horizontal"): return true
if check_placement(r, c, word, direction="vertical"): return true
# ... repeat for reversed word
return falseWhy this fails
While this approach is logically sound, the implementation complexity is high due to the numerous boundary checks required for the "exact fit" constraint at every single cell. It leads to redundant checks; for example, if a row has 10 empty spaces, the brute force might attempt to validate the word starting at index 0, then index 1, etc., repeatedly scanning the same row segments. The time complexity approaches where is the word length, which is acceptable but inefficient and error-prone to implement during an interview.
Algorithm Strategy: Backtracking Patterns
We will systematically enumerate all possible "paths" (segments) in the grid.
- Directional Iteration: We need to check horizontal slots and vertical slots. We can handle vertical slots by simply transposing the matrix (swapping rows and columns) and reusing the horizontal logic.
- Segmentation: For each row, we treat
#as a delimiter. We split the row into a list of token strings. - Constraint Enforcement:
- Length Constraint: If a token's length does not equal
word.length, discard it immediately. - Content Constraint: If the length matches, check if the token can form the
word.
- Length Constraint: If a token's length does not equal
- Matching Logic: A token matches the word if, for all indices :
token[i]is a space' ', ORtoken[i]is equal toword[i].- We must check this against
word(left-to-right placement) andreversed(word)(right-to-left placement).
Execution Flow
- Normalize Input: Create a list of configurations to check. This usually includes the original
boardand the transposedboard. - Traverse Rows: Iterate through each row of the current configuration.
- Identify Segments:
- Traverse the row element by element.
- Accumulate characters into a current segment buffer.
- When a
#is encountered (or end of row), consider the accumulated segment complete.
- Validate Segment:
- If the segment length equals
word.length:- Check if segment matches
word. - Check if segment matches
reverse(word). - If either is true, return
true.
- Check if segment matches
- Reset the segment buffer and continue.
- If the segment length equals
- Termination: If all rows and all transposed rows (columns) are checked without a match, return
false.
Proof of Correctness
The algorithm is correct because it exhaustively partitions the grid into all possible contiguous slots bounded by # or edges. By definition of the problem, the word must occupy exactly one such full slot.
- Completeness: By checking every row and every column, and splitting by
#, we identify every possible physical location the word could fit. - Validity: The length check enforces the boundary constraints (cannot be a substring of a larger space). The character comparison enforces the crossword conflict rules.
- Orientation: Checking both
wordandreversed(word)covers all 4 directional possibilities (L->R, R->L, T->B, B->T).
Pattern Reuse Notes
The "Backtracking / Path Finding in Grid" pattern used here is a fundamental technique.
- LeetCode 79: Word Search: Uses the same grid traversal concepts but allows turns (non-linear paths).
- LeetCode 212: Word Search II: Extends the pattern to search for multiple words simultaneously using a Trie.
In LeetCode 2018, the "path" is constrained to be a straight line, making it a simplified, iterative version of the more complex DFS-based word search problems.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 2018
1class Solution {
2public:
3 bool placeWordInCrossword(vector<vector<char>>& board, string word) {
4 int m = board.size();
5 int n = board[0].size();
6
7 // Check rows
8 for (const auto& row : board) {
9 if (checkLine(row, word)) return true;
10 }
11
12 // Check columns by creating vertical lines
13 for (int j = 0; j < n; ++j) {
14 vector<char> col;
15 col.reserve(m);
16 for (int i = 0; i < m; ++i) {
17 col.push_back(board[i][j]);
18 }
19 if (checkLine(col, word)) return true;
20 }
21
22 return false;
23 }
24
25private:
26 // Helper to check if word fits in any segment of a line (row or col)
27 bool checkLine(const vector<char>& line, const string& word) {
28 int n = line.size();
29 int len = word.length();
30 string revWord = word;
31 reverse(revWord.begin(), revWord.end());
32
33 // Iterate through the line finding segments between '#'
34 for (int i = 0; i < n; ) {
35 if (line[i] == '#') {
36 i++;
37 continue;
38 }
39
40 int j = i;
41 // Find end of current segment
42 while (j < n && line[j] != '#') {
43 j++;
44 }
45
46 // If segment length matches word length, check compatibility
47 if (j - i == len) {
48 if (matches(line, i, j, word) || matches(line, i, j, revWord)) {
49 return true;
50 }
51 }
52
53 i = j; // Move to next segment
54 }
55 return false;
56 }
57
58 // Check if line[start...end] is compatible with target word
59 bool matches(const vector<char>& line, int start, int end, const string& target) {
60 for (int k = 0; k < target.length(); ++k) {
61 char boardChar = line[start + k];
62 if (boardChar != ' ' && boardChar != target[k]) {
63 return false;
64 }
65 }
66 return true;
67 }
68};Java Solution for LeetCode 2018
1class Solution {
2 public boolean placeWordInCrossword(char[][] board, String word) {
3 // Check Horizontal rows
4 for (char[] row : board) {
5 if (checkLine(row, word)) return true;
6 }
7
8 // Check Vertical columns
9 int m = board.length;
10 int n = board[0].length;
11 for (int j = 0; j < n; j++) {
12 char[] col = new char[m];
13 for (int i = 0; i < m; i++) {
14 col[i] = board[i][j];
15 }
16 if (checkLine(col, word)) return true;
17 }
18
19 return false;
20 }
21
22 private boolean checkLine(char[] line, String word) {
23 int n = line.length;
24 int len = word.length();
25
26 for (int i = 0; i < n; ) {
27 if (line[i] == '#') {
28 i++;
29 continue;
30 }
31
32 int j = i;
33 while (j < n && line[j] != '#') {
34 j++;
35 }
36
37 // Check segment [i, j)
38 if (j - i == len) {
39 if (matches(line, i, word) || matchesReverse(line, i, word)) {
40 return true;
41 }
42 }
43
44 i = j;
45 }
46 return false;
47 }
48
49 private boolean matches(char[] line, int start, String word) {
50 for (int k = 0; k < word.length(); k++) {
51 char c = line[start + k];
52 if (c != ' ' && c != word.charAt(k)) return false;
53 }
54 return true;
55 }
56
57 private boolean matchesReverse(char[] line, int start, String word) {
58 for (int k = 0; k < word.length(); k++) {
59 char c = line[start + k];
60 // Compare with word from end to start
61 if (c != ' ' && c != word.charAt(word.length() - 1 - k)) return false;
62 }
63 return true;
64 }
65}Python Solution for LeetCode 2018
1class Solution:
2 def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
3 n = len(word)
4
5 # Generator to yield all rows and all columns
6 # zip(*board) transposes the board to treat columns as rows
7 lines = list(board) + list(zip(*board))
8
9 for line in lines:
10 # Join the line into a string and split by obstacle '#'
11 # This gives us all valid continuous segments
12 segments = "".join(line).split("#")
13
14 for segment in segments:
15 # Optimization: Only check segments of the correct length
16 if len(segment) == n:
17 # Check forward match
18 if all(s == ' ' or s == w for s, w in zip(segment, word)):
19 return True
20 # Check backward match
21 if all(s == ' ' or s == w for s, w in zip(segment, word[::-1])):
22 return True
23
24 return False