# LeetCode 79: Word Search

## Problem Restatement

We are given an `m x n` grid of characters called `board` and a string called `word`.

We need to return `True` if `word` can be formed by walking through the grid.

The walk must follow these rules:

| Rule | Meaning |
|---|---|
| Sequential letters | The first visited cell must match `word[0]`, the next must match `word[1]`, and so on |
| Adjacent cells only | We may move up, down, left, or right |
| No diagonal movement | Diagonal cells do not count as adjacent |
| No repeated cell | The same board cell cannot be used more than once in one word path |

The official statement asks whether `word` exists in the grid, where adjacent cells are horizontally or vertically neighboring, and the same cell may not be used more than once. The common examples include `board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]`, where `"ABCCED"` returns `true`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A 2D character grid `board` and a string `word` |
| Output | `True` if `word` can be formed, otherwise `False` |
| Movement | Up, down, left, right |
| Restriction | A cell may be used at most once in the current path |

Function shape:

```python
class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        ...
```

## Examples

Example 1:

```python
board = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"],
]
word = "ABCCED"
```

One valid path is:

```python
A -> B -> C -> C -> E -> D
```

So the answer is:

```python
True
```

Example 2:

```python
board = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"],
]
word = "SEE"
```

One valid path is:

```python
S -> E -> E
```

So the answer is:

```python
True
```

Example 3:

```python
board = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"],
]
word = "ABCB"
```

The path would need to reuse the first `B`.

That is not allowed.

So the answer is:

```python
False
```

## First Thought: Try Every Starting Cell

The word can begin at any cell whose character matches `word[0]`.

So a natural first idea is:

1. Try every cell as a starting point.
2. From that cell, search for the next character.
3. Continue until the whole word is matched.

This is a graph search problem on a grid.

Each cell has up to four neighbors:

```python
up, down, left, right
```

Since we may need to undo choices when a path fails, the search needs backtracking.

## Key Insight

At each step, we are trying to match:

```python
word[index]
```

at position:

```python
board[row][col]
```

A recursive search can answer this question:

“Can we match `word[index:]` starting from cell `(row, col)`?”

If the current cell does not match `word[index]`, this path fails.

If it matches, we temporarily mark the cell as used, then try the four neighbors for `word[index + 1]`.

After trying those neighbors, we restore the cell so it can be used in a different path.

That restore step is the backtracking step.

## Algorithm

Let:

```python
rows = len(board)
cols = len(board[0])
```

Define a DFS function:

```python
dfs(row, col, index)
```

It returns whether we can match `word[index:]` starting from `(row, col)`.

Inside `dfs`:

1. If `index == len(word)`, all characters are matched.
2. If `(row, col)` is outside the board, return `False`.
3. If `board[row][col] != word[index]`, return `False`.
4. Temporarily mark `board[row][col]` as visited.
5. Recursively search the four neighboring cells for `index + 1`.
6. Restore the original character.
7. Return whether any neighbor worked.

The outer function tries every cell as a starting position.

If any starting position works, return `True`.

Otherwise, return `False`.

## Walkthrough

Use this board:

```python
board = [
    ["A", "B", "C", "E"],
    ["S", "F", "C", "S"],
    ["A", "D", "E", "E"],
]
word = "ABCCED"
```

Start at cell `(0, 0)`:

```python
board[0][0] = "A"
word[0] = "A"
```

This matches.

Now we need `word[1]`, which is `"B"`.

From `(0, 0)`, the valid neighboring cells are:

```python
(1, 0) = "S"
(0, 1) = "B"
```

The cell `(0, 1)` matches `"B"`.

Now we need `"C"`.

From `(0, 1)`, move to `(0, 2)`:

```python
board[0][2] = "C"
```

Now we need another `"C"`.

From `(0, 2)`, move to `(1, 2)`:

```python
board[1][2] = "C"
```

Now we need `"E"`.

From `(1, 2)`, move to `(2, 2)`:

```python
board[2][2] = "E"
```

Now we need `"D"`.

From `(2, 2)`, move to `(2, 1)`:

```python
board[2][1] = "D"
```

All characters are matched, so the answer is `True`.

## Correctness

The DFS only accepts a cell when its character equals the current character in `word`.

Therefore, every path accepted by the algorithm spells the word in the correct order.

The DFS only moves to one of four neighbors:

```python
(row + 1, col)
(row - 1, col)
(row, col + 1)
(row, col - 1)
```

Therefore, every accepted path uses only horizontally or vertically adjacent cells.

Before exploring neighbors, the algorithm marks the current cell as visited. While that recursive path is active, the same cell cannot be used again. Therefore, every accepted path uses each cell at most once.

Now consider any valid path that exists in the board. The outer loop tries the first cell of that path as a starting cell. From there, the DFS tries all four legal directions at each step. Since the valid path uses only legal moves and matching characters, the DFS can follow that exact path and eventually match every character.

So if a valid path exists, the algorithm returns `True`. If the algorithm returns `True`, it has found a path satisfying all rules. Therefore, the algorithm is correct.

## Complexity

Let:

```python
R = number of rows
C = number of columns
L = len(word)
```

From each cell, DFS may branch into up to four directions for the first move. After that, it usually has at most three useful directions because it cannot immediately go back to the previous cell.

A tight common bound is:

```python
O(R * C * 4 * 3^(L - 1))
```

A simpler upper bound is:

```python
O(R * C * 4^L)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(R * C * 4 * 3^(L - 1))` | Try each starting cell, then backtrack through possible paths |
| Space | `O(L)` | Recursion depth is at most the word length |

The implementation below marks cells in place, so it does not need a separate visited set.

## Implementation

```python
class Solution:
    def exist(self, board: list[list[str]], word: str) -> bool:
        rows = len(board)
        cols = len(board[0])

        def dfs(row: int, col: int, index: int) -> bool:
            if index == len(word):
                return True

            if row < 0 or row >= rows:
                return False

            if col < 0 or col >= cols:
                return False

            if board[row][col] != word[index]:
                return False

            original = board[row][col]
            board[row][col] = "#"

            found = (
                dfs(row + 1, col, index + 1)
                or dfs(row - 1, col, index + 1)
                or dfs(row, col + 1, index + 1)
                or dfs(row, col - 1, index + 1)
            )

            board[row][col] = original
            return found

        for row in range(rows):
            for col in range(cols):
                if dfs(row, col, 0):
                    return True

        return False
```

## Code Explanation

We first store the board size:

```python
rows = len(board)
cols = len(board[0])
```

The helper function receives a cell and the current index in `word`:

```python
def dfs(row: int, col: int, index: int) -> bool:
```

If `index == len(word)`, then every character has been matched:

```python
if index == len(word):
    return True
```

Then we reject invalid cells:

```python
if row < 0 or row >= rows:
    return False

if col < 0 or col >= cols:
    return False
```

Then we reject mismatched characters:

```python
if board[row][col] != word[index]:
    return False
```

If the cell matches, we save its original character:

```python
original = board[row][col]
```

Then we mark it as visited:

```python
board[row][col] = "#"
```

This works because the board contains English letters, so `"#"` cannot be confused with a valid board character.

Then we try all four legal directions:

```python
found = (
    dfs(row + 1, col, index + 1)
    or dfs(row - 1, col, index + 1)
    or dfs(row, col + 1, index + 1)
    or dfs(row, col - 1, index + 1)
)
```

If any direction works, `found` becomes `True`.

Before returning, we restore the cell:

```python
board[row][col] = original
```

This is necessary because the same cell may be used in a different starting path or a different branch.

The outer loop tries all starting cells:

```python
for row in range(rows):
    for col in range(cols):
        if dfs(row, col, 0):
            return True
```

If none works, the word does not exist:

```python
return False
```

## Testing

```python
def run_tests():
    s = Solution()

    board1 = [
        ["A", "B", "C", "E"],
        ["S", "F", "C", "S"],
        ["A", "D", "E", "E"],
    ]

    assert s.exist([row[:] for row in board1], "ABCCED") is True
    assert s.exist([row[:] for row in board1], "SEE") is True
    assert s.exist([row[:] for row in board1], "ABCB") is False

    board2 = [["A"]]
    assert s.exist([row[:] for row in board2], "A") is True
    assert s.exist([row[:] for row in board2], "B") is False

    board3 = [
        ["C", "A", "A"],
        ["A", "A", "A"],
        ["B", "C", "D"],
    ]
    assert s.exist([row[:] for row in board3], "AAB") is True

    board4 = [
        ["A", "B"],
        ["C", "D"],
    ]
    assert s.exist([row[:] for row in board4], "AD") is False

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"ABCCED"` | Main valid path |
| `"SEE"` | Valid path with repeated letter values in different cells |
| `"ABCB"` | Would require reusing a cell |
| Single-cell board | Minimum board size |
| `"AAB"` on a dense board | Confirms backtracking can change route |
| `"AD"` on a 2x2 board | Confirms diagonal movement is not allowed |