> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Word Search Python Solution with Tests

> Tested Python solution for LeetCode 79 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 79, Medium. Topics: Array, String, Backtracking, Depth-First Search, Matrix. [View on LeetCode](https://leetcode.com/problems/word-search/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 79   # by problem number
lcpy gen -s word_search   # by problem name
```

## Problem

Given an `m x n` grid of characters `board` and a string `word`, return `true` *if* `word` *exists in the grid*.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

### Examples

![Word Search Example 1](https://assets.leetcode.com/uploads/2020/11/04/word2.jpg)

```
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true
```

![Word Search Example 2](https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg)

```
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true
```

![Word Search Example 3](https://assets.leetcode.com/uploads/2020/10/15/word3.jpg)

```
Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false
```

### Constraints

* `m == board.length`
* `n = board[i].length`
* `1 <= m, n <= 6`
* `1 <= word.length <= 15`
* `board` and `word` consists of only lowercase and uppercase English letters.

**Follow up:** Could you use search pruning to make your solution faster with a larger `board`?

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/word_search/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/word_search/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import Counter


class Solution:
    # Time: O(m*n*4^L) where L is word length
    # Space: O(L)
    def exist(self, board: list[list[str]], word: str) -> bool:
        m, n = len(board), len(board[0])

        # Early pruning: check if board has enough characters
        board_counter = Counter(ch for row in board for ch in row)
        word_counter = Counter(word)
        for ch in word_counter:
            if board_counter[ch] < word_counter[ch]:
                return False

        # Optimization: start from less frequent end
        if board_counter[word[0]] > board_counter[word[-1]]:
            word = word[::-1]

        def dfs(i: int, j: int, k: int) -> bool:
            if k == len(word):
                return True
            if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
                return False

            temp = board[i][j]
            board[i][j] = "#"
            for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                if dfs(i + di, j + dj, k + 1):
                    board[i][j] = temp
                    return True
            board[i][j] = temp
            return False

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False
```

## Complexity

| Time                              | Space |
| --------------------------------- | ----- |
| O(m*n*4^L) where L is word length | O(L)  |

## Tags

[Grind 75](/catalog/grind-75), [Grind](/catalog/grind), [Blind 75](/catalog/blind-75), [NeetCode 150](/catalog/neetcode-150), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).