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

> Tested Python solution for LeetCode 140 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 140, Hard. Topics: Array, Hash Table, String, Dynamic Programming, Backtracking, Trie, Memoization. [View on LeetCode](https://leetcode.com/problems/word-break-ii/description/).

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

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

## Problem

Given a string `s` and a dictionary of strings `wordDict`, add spaces in `s` to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in **any order**.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

### Examples

```
Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]
```

**Explanation:** The following are all of the possible valid segmentations:

* "cats and dog"
* "cat sand dog"

```
Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
```

**Explanation:** Note that you are allowed to reuse a dictionary word.

```
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: []
```

### Constraints

* 1 \<= s.length \<= 20
* 1 \<= wordDict.length \<= 1000
* 1 \<= wordDict\[i].length \<= 10
* `s` and `wordDict[i]` consist of only lowercase English letters.
* All the strings of `wordDict` are unique.
* Input is generated in a way that the length of the answer doesn't exceed 10^5.

## Solution

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

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(2^n * n) worst case (all segmentations), bounded by answer size
    # Space: O(n * 2^n) for memo storage
    def word_break(self, s: str, word_dict: list[str]) -> list[str]:
        words = set(word_dict)

        # Memo: index -> list of sentences covering s[index:]
        memo: dict[int, list[str]] = {}

        def backtrack(start: int) -> list[str]:
            if start == len(s):
                return [""]

            if start in memo:
                return memo[start]

            sentences: list[str] = []
            for end in range(start + 1, len(s) + 1):
                word = s[start:end]
                if word in words:
                    for sub_sentence in backtrack(end):
                        if sub_sentence:
                            sentences.append(word + " " + sub_sentence)
                        else:
                            sentences.append(word)

            memo[start] = sentences
            return sentences

        return backtrack(0)
```

## Complexity

| Time                                                               | Space                        |
| ------------------------------------------------------------------ | ---------------------------- |
| O(2^n \* n) worst case (all segmentations), bounded by answer size | O(n \* 2^n) for memo storage |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).