# Word Break

- **Canonical ID**: `word-break`
- **Canonical URL**: https://dsacheatsheet.com/problems/word-break
- **Difficulty**: medium
- **Patterns**: 1D DP, Strings
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/word-break/

## 1. Core Invariant / The Trick

Define `dp[i] = True` iff prefix `s[:i]` can be segmented. Instead of checking every split `0..i`, probe each word `w` in `wordDict` backward from `i` (`dp[i - len(w)] and s[i-len(w):i] == w`) with a hash set or bounded lengths.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N * W * L)`
- **Space Complexity**: `O(N)`
- **Proof**: For each prefix end `i in 1..N`, matches only existing dictionary words in `O(W * L)` or unique lengths `L`.

## 3. Minimal Idiomatic Code

### Python
```python
def wordBreak(s: str, wordDict: list[str]) -> bool:
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for w in wordDict:
            if i >= len(w) and dp[i - len(w)] and s[i - len(w):i] == w:
                dp[i] = True
                break
    return dp[n]
```

### TypeScript
```typescript
export function wordBreak(s: string, wordDict: string[]): boolean {
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (const w of wordDict) {
      if (i >= w.length && dp[i - w.length] && s.slice(i - w.length, i) === w) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}
```

### C++
```cpp
bool wordBreak(string s, vector<string>& wordDict) {
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;
    for (size_t i = 1; i <= s.size(); ++i) {
        for (const auto& w : wordDict) {
            if (i >= w.size() && dp[i - w.size()] && s.compare(i - w.size(), w.size(), w) == 0) {
                dp[i] = true; break;
            }
        }
    }
    return dp[s.size()];
}
```

### Java
```java
boolean wordBreak(String s, List<String> wordDict) {
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (String w : wordDict) {
            if (i >= w.length() && dp[i - w.length()] && s.startsWith(w, i - w.length())) {
                dp[i] = true; break;
            }
        }
    }
    return dp[s.length()];
}
```

### Go
```go
func wordBreak(s string, wordDict []string) bool {
    dp := make([]bool, len(s)+1)
    dp[0] = true
    for i := 1; i <= len(s); i++ {
        for _, w := range wordDict {
            if i >= len(w) && dp[i-len(w)] && s[i-len(w):i] == w { dp[i] = true; break }
        }
    }
    return dp[len(s)]
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Greedy prefix matching fails when a longer dictionary word hides a valid split (e.g. `"cars"` vs `["car","ca","rs"]`).

### Follow-ups
- Word Break II adds memoized path reconstruction (or Trie + DP pruning) to enumerate all sentences.