# LeetCode 139: Word Break

## Problem Restatement

We are given:

| Name | Meaning |
|---|---|
| `s` | A string we want to split |
| `wordDict` | A list of valid dictionary words |

Return `True` if `s` can be segmented into a sequence of one or more dictionary words.

The same dictionary word may be used multiple times.

If no complete segmentation exists, return `False`.

LeetCode states the task as checking whether `s` can be segmented into a space-separated sequence of dictionary words. Words may be reused, and dictionary words are unique.

## Examples

Example 1:

```python
s = "leetcode"
wordDict = ["leet", "code"]
```

We can split:

```text
leet | code
```

Output:

```python
True
```

Example 2:

```python
s = "applepenapple"
wordDict = ["apple", "pen"]
```

We can split:

```text
apple | pen | apple
```

The word `"apple"` is reused.

Output:

```python
True
```

Example 3:

```python
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
```

There is no way to split the whole string into valid dictionary words.

Output:

```python
False
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `s: str`, `wordDict: list[str]` |
| Output | `bool` |
| Rule | Every segment must be in `wordDict` |
| Reuse | Dictionary words may be reused |
| Goal | Decide whether a full segmentation exists |

Function shape:

```python
class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        ...
```

## First Thought: Try Every Split Recursively

A direct approach is to try every dictionary word at the current position.

For example:

```python
s = "leetcode"
wordDict = ["leet", "code"]
```

At index `0`, we can choose `"leet"` because the string starts with it.

Then we recurse on:

```python
"code"
```

This works conceptually, but it repeats work.

For a string with many possible prefixes, the recursion branches heavily.

Example:

```python
s = "aaaaaaa"
wordDict = ["a", "aa", "aaa", "aaaa"]
```

There are many ways to split the same suffix again and again.

We need dynamic programming.

## Key Insight

A prefix is breakable if it can be split into:

```text
breakable prefix + dictionary word
```

Let:

```python
dp[i]
```

mean:

```text
s[0:i] can be segmented into dictionary words
```

This uses Python slice notation, where `s[0:i]` excludes index `i`.

So:

| State | Meaning |
|---|---|
| `dp[0]` | Empty prefix is breakable |
| `dp[1]` | `s[0:1]` is breakable |
| `dp[n]` | The whole string is breakable |

The answer is:

```python
dp[len(s)]
```

## DP Transition

To compute `dp[i]`, try every split point `j` before `i`.

```text
s[0:i] = s[0:j] + s[j:i]
```

If:

```python
dp[j] == True
```

and:

```python
s[j:i] in word_set
```

then `dp[i]` is also `True`.

So the transition is:

```python
dp[i] = any(dp[j] and s[j:i] in word_set for j in range(i))
```

## Algorithm

Convert `wordDict` into a set:

```python
word_set = set(wordDict)
```

Create a boolean array:

```python
dp = [False] * (n + 1)
```

Set:

```python
dp[0] = True
```

Then for each end index `i` from `1` to `n`:

1. Try every split point `j` from `0` to `i - 1`.
2. If `dp[j]` is true and `s[j:i]` is in the dictionary, set `dp[i] = True`.
3. Stop early for this `i`.

Return `dp[n]`.

## Correctness

`dp[0]` is true because the empty prefix needs no words.

For every `i > 0`, the algorithm checks every possible last word of a segmentation of `s[0:i]`.

If there is a valid segmentation, then it has some last word `s[j:i]`. The prefix before it, `s[0:j]`, must also be segmentable, so `dp[j]` is true. Since the last word is in the dictionary, the algorithm will set `dp[i]` to true.

If the algorithm sets `dp[i]` to true, then there is some split point `j` where `dp[j]` is true and `s[j:i]` is a dictionary word. Therefore, a valid segmentation of `s[0:j]` followed by `s[j:i]` gives a valid segmentation of `s[0:i]`.

Thus, each `dp[i]` correctly says whether `s[0:i]` can be segmented. Therefore, `dp[n]` is the correct answer for the whole string.

## Complexity

Let:

| Symbol | Meaning |
|---|---|
| `n` | Length of `s` |
| `L` | Maximum dictionary word length |

Basic DP tries all split points.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^3)` in Python slicing model | There are `O(n^2)` substrings, and slicing can cost `O(n)` |
| Space | `O(n + dictionary size)` | DP array and dictionary set |

We can improve practical runtime by only checking split lengths up to the longest dictionary word.

Then each `i` checks at most `L` candidates.

| Metric | Value |
|---|---:|
| Time | `O(n * L^2)` with slicing |
| Space | `O(n + dictionary size)` |

Since LeetCode constraints are small enough for this DP, this approach is accepted.

## Implementation

```python
class Solution:
    def wordBreak(self, s: str, wordDict: list[str]) -> bool:
        word_set = set(wordDict)
        max_len = max(len(word) for word in wordDict)

        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        for end in range(1, n + 1):
            start_limit = max(0, end - max_len)

            for start in range(start_limit, end):
                if not dp[start]:
                    continue

                if s[start:end] in word_set:
                    dp[end] = True
                    break

        return dp[n]
```

## Code Explanation

We store dictionary words in a set:

```python
word_set = set(wordDict)
```

This makes membership checks fast.

We also compute the maximum dictionary word length:

```python
max_len = max(len(word) for word in wordDict)
```

No valid last word can be longer than this.

The DP array has `n + 1` entries:

```python
dp = [False] * (n + 1)
```

The empty prefix is always segmentable:

```python
dp[0] = True
```

For each end position:

```python
for end in range(1, n + 1):
```

we only need to try starts that form a word of length at most `max_len`:

```python
start_limit = max(0, end - max_len)
```

If the prefix before `start` cannot be segmented, skip it:

```python
if not dp[start]:
    continue
```

If the last substring is a dictionary word:

```python
if s[start:end] in word_set:
```

then this prefix is breakable:

```python
dp[end] = True
break
```

The final answer is:

```python
return dp[n]
```

## Testing

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

    assert s.wordBreak("leetcode", ["leet", "code"]) is True

    assert s.wordBreak(
        "applepenapple",
        ["apple", "pen"],
    ) is True

    assert s.wordBreak(
        "catsandog",
        ["cats", "dog", "sand", "and", "cat"],
    ) is False

    assert s.wordBreak(
        "aaaaaaa",
        ["aaaa", "aaa"],
    ) is True

    assert s.wordBreak(
        "cars",
        ["car", "ca", "rs"],
    ) is True

    assert s.wordBreak(
        "bb",
        ["a", "b", "bbb", "bbbb"],
    ) is True

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `"leetcode"` | Basic split into two words |
| `"applepenapple"` | Reuses a dictionary word |
| `"catsandog"` | Similar words but no full segmentation |
| `"aaaaaaa"` | Multiple overlapping word choices |
| `"cars"` | Greedy choice `"car"` would fail, but `"ca" + "rs"` works |
| `"bb"` | Reusing `"b"` works |