Count Straight-Line Occurrences of a Word in a Letter Grid, Rows and Columns Only
Company: Optiver
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
You are given a rectangular grid of lowercase letters and a target word. Count how many times the word appears in the grid when read in a straight line, either horizontally along a row or vertically down a column.
Unlike the classic word-search puzzle, a match may not turn: all letters of one occurrence lie in consecutive cells of a single row or of a single column.
### Function Signature
```python
def count_word_occurrences(grid: list[str], word: str) -> int:
```
### Rules
- `grid[i][j]` is the letter in row `i`, column `j`. Rows are numbered from the top and columns from the left.
- An occurrence is a starting cell together with a direction, either rightward along the row or downward along the column, such that the `len(word)` consecutive cells read from the start in that direction spell `word` exactly.
- Only left-to-right and top-to-bottom readings count. Reversed readings (right to left, bottom to top) and diagonals do not.
- Occurrences may overlap and share cells. Each distinct pair of starting cell and direction counts once; for example, `"aa"` occurs twice in a row that reads `"aaa"`.
- If `word` has exactly one letter, the rightward and downward readings from a cell are the same single cell, so each cell equal to that letter counts exactly once.
- A reading that would run past the edge of the grid is not an occurrence.
### Constraints
- `1 <= len(grid) <= 300`
- `1 <= len(grid[i]) <= 300`, and every row has the same length.
- `1 <= len(word) <= 300`
- `grid` and `word` contain only lowercase English letters `a` to `z`.
- The result is an integer from `0` to `2 * len(grid) * len(grid[0])`, so at most `180000`, and it is uniquely determined by the input.
### Examples
**Example 1**
- Input: `grid = ["cat", "abx", "tat"]`, `word = "cat"`
- Output: `2`
- Explanation: Row 0 reads `"cat"` from its first cell, and column 0 reads `c`, `a`, `t` downward from the same cell. They are different directions, so both count. No other row or column contains `"cat"`.
**Example 2**
- Input: `grid = ["aaa", "aab"]`, `word = "aa"`
- Output: `5`
- Explanation: Row 0 contains `"aa"` starting at columns 0 and 1, and row 1 contains it starting at column 0, for 3 horizontal occurrences. Columns 0 and 1 each read `a`, `a` downward, for 2 vertical occurrences. Column 2 reads `a`, `b`.
**Example 3**
- Input: `grid = ["ab", "dc"]`, `word = "abc"`
- Output: `0`
- Explanation: The letters `a`, `b`, `c` can be visited in order only by moving right and then down, which is a turn. Every row and column has just two cells, too short for a three-letter word.
Overview: Count how many times a target word appears in a grid of letters when read in a straight line along a row or down a column, with no turns and overlapping matches counted separately. It tests careful grid traversal, boundary handling, precise occurrence counting rules and efficient string matching.
You are given a rectangular grid of lowercase letters as a list of equal-length strings, and a target word. Count how many times the word appears in the grid when read in a straight line, either rightward along a row or downward along a column. Unlike the classic word-search puzzle, an occurrence may not turn: all of its letters lie in consecutive cells of a single row or of a single column.
Implement `count_word_occurrences(grid, word)` and return the number of occurrences as an integer.
### Rules
- `grid[i][j]` is the letter in row `i`, column `j`. Rows are numbered from the top and columns from the left.
- An occurrence is a starting cell together with a direction, either rightward along the row or downward along the column, such that the `len(word)` consecutive cells read from the start in that direction spell `word` exactly.
- Only left-to-right and top-to-bottom readings count. Reversed readings (right to left, bottom to top) and diagonals do not.
- Occurrences may overlap and share cells. Each distinct pair of starting cell and direction counts once; for example, `"aa"` occurs twice in a row that reads `"aaa"`.
- If `word` has exactly one letter, the rightward and downward readings from a cell are the same single cell, so each cell equal to that letter counts exactly once.
- A reading that would run past the edge of the grid is not an occurrence.
- The answer is a single integer and is uniquely determined by the input.
### Example 1
- Input: `grid = ["cat", "abx", "tat"]`, `word = "cat"`
- Output: `2`
- Explanation: Row 0 reads `"cat"` from its first cell, and column 0 reads `c`, `a`, `t` downward from the same cell. They are different directions, so both count. No other row or column contains `"cat"`.
### Example 2
- Input: `grid = ["aaa", "aab"]`, `word = "aa"`
- Output: `5`
- Explanation: Row 0 contains `"aa"` starting at columns 0 and 1, and row 1 contains it starting at column 0, for 3 horizontal occurrences. Columns 0 and 1 each read `a`, `a` downward, for 2 vertical occurrences. Column 2 reads `a`, `b`.
### Example 3
- Input: `grid = ["ab", "dc"]`, `word = "abc"`
- Output: `0`
- Explanation: The letters `a`, `b`, `c` can be visited in order only by moving right and then down, which is a turn. Every row and column has just two cells, too short for a three-letter word.
### Constraints
- `1 <= len(grid) <= 300`
- `1 <= len(grid[i]) <= 300`, and every row has the same length.
- `1 <= len(word) <= 300`
- `grid` and `word` contain only lowercase English letters `a` to `z`.
- The result is an integer from `0` to `2 * len(grid) * len(grid[0])`, so at most `180000`; it fits in a 32-bit signed integer.
Constraints
- 1 <= len(grid) <= 300
- 1 <= len(grid[i]) <= 300, and every row has the same length
- 1 <= len(word) <= 300
- grid and word contain only lowercase English letters a to z
- 0 <= result <= 2 * len(grid) * len(grid[0]) <= 180000 (fits in a 32-bit signed integer)
Examples
Input: (['cat', 'abx', 'tat'], 'cat')
Expected Output: 2
Input: (['aaa', 'aab'], 'aa')
Expected Output: 5
Hints
- Every occurrence lives entirely inside one row read left to right or one column read top to bottom, so the grid splits into independent one-dimensional strings.
- Occurrences may overlap, so after a match keep scanning from the next starting position rather than jumping past the whole word.
- Think about what happens when the word is a single letter: the rightward and downward readings from a cell are the same occurrence.