Find a Word Along One Fixed Direction in a Grid

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

board = ["ABC","DEF","GHI"]
word = "AEI"
result = true

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.

Find a Word Along One Straight Grid Direction

Approach

Enumerate each possible starting cell and each of the eight nonzero row/column step pairs. Once selected, that step remains fixed. The final position is start+(length-1)step; if it is outside the rectangular board, reject this direction. Otherwise all intervening positions are inside because each coordinate moves monotonically between its endpoints. Compare the word against those positions. A complete match is sufficient, and enumeration is necessary because every permitted straight path has exactly such a start and direction. Nonzero movement ensures cells cannot repeat. For a one-letter word the endpoint equals the start, so any matching cell succeeds. Turning and wrapping never occur in the coordinate formula. For R rows, C columns and word length K, time is O(RC*K) because eight is constant; traversal uses O(1) auxiliary state, excluding C++ argument copies.

• Time complexity: O(R * C * K)
• Space complexity: O(1) auxiliary state, excluding C++ input copies