Find a Word Along One Fixed Direction in a Grid
Company: Reddit
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Determine whether a word appears in a letter grid along one straight direction. After choosing a starting cell and direction, keep that same direction for every subsequent letter. Do not turn, jump, wrap around, or revisit a prior cell.
Implement `word_exists(board: string[], word: string) -> bool`.
### Constraints & Assumptions
- The board is rectangular, with 1 through 100 rows and columns. All characters are uppercase ASCII letters.
- The word has 1 through 100 uppercase letters.
- This practice version permits all eight nonzero adjacent directions: horizontal, vertical, and diagonal, in either orientation. The source explicitly fixes straight-line movement but does not enumerate the permitted directions.
- A one-letter word is present if any board cell contains it.
- A path must remain inside the board for its entire length.
- This is a straight-line word-search game, not a path that may change direction after each letter.
### Examples
```text
board = ["ABC","DEF","GHI"]
word = "AEI"
result = true
```
```text
board = ["ABC","DEF","GHI"]
word = "ABE"
result = false
```
`ABE` would require turning after the second letter, which is not allowed.
```hint Choose the direction once
After selecting `(dr, dc)`, the k-th letter must be at `(start_row + k*dr, start_col + k*dc)`. There is no new direction choice at later letters.
```
Overview: Search a letter grid for a word along one fixed direction, with explicit diagonal rules, boundaries, and rejection of paths that turn.
Read the full Reddit Software Engineer interview experience this question came from
Determine whether a word appears in a letter grid along one straight direction. After choosing a starting cell and direction, keep that same direction for every subsequent letter. Do not turn, jump, wrap around, or revisit a prior cell.
Implement `word_exists(board: string[], word: string) -> bool`.
### Constraints & Assumptions
- The board is rectangular, with 1 through 100 rows and columns. All characters are uppercase ASCII letters.
- The word has 1 through 100 uppercase letters.
- This practice version permits all eight nonzero adjacent directions: horizontal, vertical, and diagonal, in either orientation. The source explicitly fixes straight-line movement but does not enumerate the permitted directions.
- A one-letter word is present if any board cell contains it.
- A path must remain inside the board for its entire length.
- This is a straight-line word-search game, not a path that may change direction after each letter.
### Examples
```text
board = ["ABC","DEF","GHI"]
word = "AEI"
result = true
```
```text
board = ["ABC","DEF","GHI"]
word = "ABE"
result = false
```
`ABE` would require turning after the second letter, which is not allowed.
```hint Choose the direction once
After selecting `(dr, dc)`, the k-th letter must be at `(start_row + k*dr, start_col + k*dc)`. There is no new direction choice at later letters.
```
Constraints
- The rectangular board has 1 through 100 rows and columns; every character is uppercase ASCII.
- Word length is 1 through 100 uppercase ASCII letters.
- Permit all eight nonzero adjacent directions, retaining the same direction throughout the word.
- Every visited cell must remain inside the board; no turns, jumps, wrapping or revisits.
- A one-letter word requires any matching cell. Return a boolean indicating existence.
Examples
Input: (['ABC', 'DEF', 'GHI'], 'AEI')
Expected Output: True
Explanation: The southeast diagonal is permitted.
Input: (['ABC', 'DEF', 'GHI'], 'ABE')
Expected Output: False
Explanation: A bent path is forbidden.