Search for a Word Along Adjacent Cells of a Letter Grid Without Reusing Cells
Company: Bloomberg
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a grid of letters and a word, decide whether the word can be spelled by a path through the grid. The path starts at any cell and moves at each step to a horizontally or vertically adjacent cell, and it may use each cell at most once. The letters of the cells along the path, in order, must equal the word.
### Function Signature
```python
def word_exists(board: list[list[str]], word: str) -> bool:
```
### Rules
- Two cells are adjacent when they share an edge: up, down, left or right. Diagonal moves are not allowed.
- A cell may appear at most once in a path, even if its letter is needed again later in the word.
- Matching is case-sensitive.
- Return `True` if at least one such path exists, otherwise `False`.
### Constraints
- `1 <= rows <= 6` and `1 <= cols <= 6`, and every row has the same length.
- `1 <= len(word) <= 15`
- Every cell holds exactly one English letter, uppercase or lowercase, and `word` consists of English letters only.
### Examples
All three examples use this board; positions are `(row, column)`, counted from 0.
```text
board = [["C", "A", "T"],
["X", "R", "S"],
["B", "O", "D"]]
```
**Example 1**
```text
Input: board as above, word = "CATS"
Output: True
```
The path `(0,0) C`, `(0,1) A`, `(0,2) T`, `(1,2) S` spells the word.
**Example 2**
```text
Input: board as above, word = "TSDOR"
Output: True
```
The path `(0,2) T`, `(1,2) S`, `(2,2) D`, `(2,1) O`, `(1,1) R` spells the word.
**Example 3**
```text
Input: board as above, word = "ARA"
Output: False
```
The only `A` is at `(0,1)`. After moving to the `R` at `(1,1)`, the only adjacent `A` is the cell already used, so the word cannot be completed.
Overview: A grid search coding question: decide whether a word can be traced through a letter grid by moving between horizontally or vertically adjacent cells without reusing any cell. It tests backtracking search, bookkeeping of visited cells and pruning under small grid and word-length bounds.
Given a rectangular grid of letters `board` and a string `word`, decide whether `word` can be spelled by a path through the grid. Implement `word_exists(board, word)`.
A path starts at any cell and, at each step, moves to a cell that is horizontally or vertically adjacent to the current one. The letters of the cells along the path, read in order, must equal `word`.
**Rules**
- Two cells are adjacent when they share an edge: up, down, left or right. Diagonal moves are not allowed.
- A cell may appear at most once in a path, even if its letter is needed again later in the word.
- Matching is case-sensitive: `"a"` and `"A"` are different letters.
- Return `True` if at least one such path exists, otherwise `False` (`true` / `false` in JavaScript, Java and C++).
Each cell of `board` is a string holding exactly one letter. Positions are written `(row, column)`, counted from 0.
**Example 1**
```text
board = [["C", "A", "T"],
["X", "R", "S"],
["B", "O", "D"]]
word = "CATS"
Output: True
```
The path `(0,0) C`, `(0,1) A`, `(0,2) T`, `(1,2) S` spells the word.
**Example 2**
```text
board = the same board as Example 1
word = "ARA"
Output: False
```
The only `A` is at `(0,1)`. After moving to the `R` at `(1,1)`, the only adjacent `A` is the cell already used, so the word cannot be completed.
**Constraints**
- `1 <= rows <= 6` and `1 <= cols <= 6`, and every row has the same length.
- `1 <= len(word) <= 15`
- Every cell holds exactly one English letter, uppercase or lowercase, and `word` consists of English letters only.
Constraints
- 1 <= rows <= 6 and 1 <= cols <= 6, and every row has the same length.
- 1 <= len(word) <= 15
- Every cell holds exactly one English letter, uppercase or lowercase, and word consists of English letters only.
Examples
Input: ([['C', 'A', 'T'], ['X', 'R', 'S'], ['B', 'O', 'D']], 'CATS')
Expected Output: True
Explanation: Source example 1: (0,0) C, (0,1) A, (0,2) T, (1,2) S spells the word.
Input: ([['C', 'A', 'T'], ['X', 'R', 'S'], ['B', 'O', 'D']], 'TSDOR')
Expected Output: True
Explanation: Source example 2: turning path (0,2) T, (1,2) S, (2,2) D, (2,1) O, (1,1) R.
Hints
- From any cell, the next letter can only come from one of the at most four cells that share an edge with it; diagonal cells never count as next to each other.
- A letter that occurs twice in the word needs two different cells holding that letter, as the ARA example shows.
- Letters are compared exactly as written, so a lowercase cell never matches an uppercase letter in the word.