Word Break DP

Determine if a string can be segmented into words from a dictionary using dynamic programming.

dynamic-programming strings word-break set

Write a function `can_break(s: str, word_dict: list[str]) -> bool` that returns `True` if the string `s` can be segmented into a space-separated sequence of one or more dictionary words, all of which are present in `word_dict`. You may assume all words in `word_dict` are unique and consist of lowercase English letters. Reuse of dictionary words is allowed. The order of words in the segmentation must follow the order of characters in `s` (i.e., the concatenation of the chosen words must equal `s` exactly). Do not use regular expressions or any external libraries.

Constraints

- `1 <= len(s) <= 300`
- `0 <= len(word_dict) <= 1000`
- Each dictionary word length is between `1` and `20`
- All strings consist of lowercase English letters only
- Your solution should run efficiently for the given limits (a DP approach or equivalent is acceptable).

Example

```python
can_break("leetcode", ["leet", "code"])  # True
can_break("applepenapple", ["apple", "pen"])  # True
can_break("catsandog", ["cats", "dog", "sand", "and", "cat"])  # False
```

20 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of the subproblem `dp[i]`: can the prefix `s[:i]` be segmented?

For each `i`, try all dictionary words that match the suffix ending at `i`.

Initialize `dp[0] = True` because the empty prefix is trivially segmentable.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.