For every cell in the matrix, the algorithm:

1. Attempts to place the word horizontally (left-to-right).
2. Attempts to place the word horizontally (right-to-left).
3. Attempts to place the word vertically (top-to-bottom).
4. Attempts to place the word vertically (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

text
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 false

Why 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 $O(M \times N \times K)$ where $K$ is the word length, which is acceptable but inefficient and error-prone to implement during an interview.

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:

1. "a " (length 2)
2. " " (length 3)

Instead of asking "Can I start the word at $(0,0)$?", 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 $i$, 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.

Execution Flow

1. Normalize Input: Create a list of configurations to check. This usually includes the original board and the transposed board.
2. Traverse Rows: Iterate through each row of the current configuration.
3. 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.
4. 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.
   • Reset the segment buffer and continue.
5. 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 word and reversed(word) covers all 4 directional possibilities (L->R, R->L, T->B, B->T).

Reference Implementation

C++ Solution for LeetCode 2018

cpp
class Solution {
public:
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        
        // Check rows
        for (const auto& row : board) {
            if (checkLine(row, word)) return true;
        }
        
        // Check columns by creating vertical lines
        for (int j = 0; j < n; ++j) {
            vector<char> col;
            col.reserve(m);
            for (int i = 0; i < m; ++i) {
                col.push_back(board[i][j]);
            }
            if (checkLine(col, word)) return true;
        }
        
        return false;
    }

private:
    // Helper to check if word fits in any segment of a line (row or col)
    bool checkLine(const vector<char>& line, const string& word) {
        int n = line.size();
        int len = word.length();
        string revWord = word;
        reverse(revWord.begin(), revWord.end());
        
        // Iterate through the line finding segments between '#'
        for (int i = 0; i < n; ) {
            if (line[i] == '#') {
                i++;
                continue;
            }
            
            int j = i;
            // Find end of current segment
            while (j < n && line[j] != '#') {
                j++;
            }
            
            // If segment length matches word length, check compatibility
            if (j - i == len) {
                if (matches(line, i, j, word) || matches(line, i, j, revWord)) {
                    return true;
                }
            }
            
            i = j; // Move to next segment
        }
        return false;
    }
    
    // Check if line[start...end] is compatible with target word
    bool matches(const vector<char>& line, int start, int end, const string& target) {
        for (int k = 0; k < target.length(); ++k) {
            char boardChar = line[start + k];
            if (boardChar != ' ' && boardChar != target[k]) {
                return false;
            }
        }
        return true;
    }
};

Java Solution for LeetCode 2018

java
class Solution {
    public boolean placeWordInCrossword(char[][] board, String word) {
        // Check Horizontal rows
        for (char[] row : board) {
            if (checkLine(row, word)) return true;
        }
        
        // Check Vertical columns
        int m = board.length;
        int n = board[0].length;
        for (int j = 0; j < n; j++) {
            char[] col = new char[m];
            for (int i = 0; i < m; i++) {
                col[i] = board[i][j];
            }
            if (checkLine(col, word)) return true;
        }
        
        return false;
    }
    
    private boolean checkLine(char[] line, String word) {
        int n = line.length;
        int len = word.length();
        
        for (int i = 0; i < n; ) {
            if (line[i] == '#') {
                i++;
                continue;
            }
            
            int j = i;
            while (j < n && line[j] != '#') {
                j++;
            }
            
            // Check segment [i, j)
            if (j - i == len) {
                if (matches(line, i, word) || matchesReverse(line, i, word)) {
                    return true;
                }
            }
            
            i = j;
        }
        return false;
    }
    
    private boolean matches(char[] line, int start, String word) {
        for (int k = 0; k < word.length(); k++) {
            char c = line[start + k];
            if (c != ' ' && c != word.charAt(k)) return false;
        }
        return true;
    }
    
    private boolean matchesReverse(char[] line, int start, String word) {
        for (int k = 0; k < word.length(); k++) {
            char c = line[start + k];
            // Compare with word from end to start
            if (c != ' ' && c != word.charAt(word.length() - 1 - k)) return false;
        }
        return true;
    }
}

Python Solution for LeetCode 2018

python
class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        n = len(word)
        
        # Generator to yield all rows and all columns
        # zip(*board) transposes the board to treat columns as rows
        lines = list(board) + list(zip(*board))
        
        for line in lines:
            # Join the line into a string and split by obstacle '#'
            # This gives us all valid continuous segments
            segments = "".join(line).split("#")
            
            for segment in segments:
                # Optimization: Only check segments of the correct length
                if len(segment) == n:
                    # Check forward match
                    if all(s == ' ' or s == w for s, w in zip(segment, word)):
                        return True
                    # Check backward match
                    if all(s == ' ' or s == w for s, w in zip(segment, word[::-1])):
                        return True
                        
        return False