> ## 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 II Python Solution with Tests

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

LeetCode 212, Hard. Topics: Array, String, Backtracking, Trie, Matrix. [View on LeetCode](https://leetcode.com/problems/word-search-ii/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 212   # by problem number
lcpy gen -s word_search_ii   # by problem name
```

## Problem

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must 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 in a word.

### Examples

```
Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
```

**Explanation:** The words "eat" and "oath" can be found on the board.

```
Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []
```

**Explanation:** The word "abcb" cannot be found on the board.

### Constraints

* m == board.length
* n == board\[i].length
* 1 \<= m, n \<= 12
* board\[i]\[j] is a lowercase English letter.
* 1 \<= words.length \<= 3 \* 10^4
* 1 \<= words\[i].length \<= 10
* words\[i] consists of lowercase English letters.
* All the strings of words are unique.

## Solution

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

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class TrieNode:
    def __init__(self):
        self.children = {}
        self.word = None


class Solution:
    def find_words(self, board: list[list[str]], words: list[str]) -> list[str]:
        """
        Optimized version with early termination and word removal.

        Time: O(m*n*4^L) where m*n is board size, L is max word length
        Space: O(W*L) where W is number of words, L is max word length
        """
        if not board or not board[0] or not words:
            return []

        # Build trie
        root = TrieNode()
        for word in words:
            node = root
            for char in word:
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
            node.word = word

        m, n = len(board), len(board[0])
        result = set()

        def dfs(i: int, j: int, node: TrieNode) -> None:
            if i < 0 or i >= m or j < 0 or j >= n:
                return

            char = board[i][j]
            if char not in node.children:
                return

            node = node.children[char]
            if node.word:
                result.add(node.word)
                # Remove word from trie to avoid duplicates
                node.word = None

            # Mark as visited
            board[i][j] = "#"

            # Explore all 4 directions
            for di, dj in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                dfs(i + di, j + dj, node)

            # Restore
            board[i][j] = char

        # Try starting from each cell
        for i in range(m):
            for j in range(n):
                dfs(i, j, root)

        return list(result)
```

## Complexity

| Time | Space |
| ---- | ----- |
| -    | -     |

## Tags

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