Word Break

Longest Increasing Subsequence

Number of Islands

Determine whether a string can be segmented into words from a dictionary.

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words.

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

## Example
```
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
```

**Constraints**
- `1 <= s.length <= 300`
- `1 <= wordDict.length <= 1000`
- `1 <= wordDict[i].length <= 20`
- `s` and `wordDict[i]` consist of only lowercase English letters.
- All the strings of `wordDict` are unique.

**Follow-up**
How would you modify the DP to return one valid segmentation (the actual list of words), not just whether one exists?

- You are given a string `s` and a list of valid words `wordDict`.
- You must decide if `s` can be cut into pieces where every piece is a dictionary word.
- Words can be reused, and you must use the whole string with no leftover characters.

Understanding the Problem

- Whether `s` is breakable depends on whether some prefix is a word **and** the remaining suffix is also breakable.
- The same suffix gets asked about repeatedly, so plain recursion does duplicated work.
- This overlap is the signal to use dynamic programming.

Spotting Overlapping Subproblems

- Let `dp[i]` mean "the first `i` characters `s[0:i]` can be segmented".
- `dp[0]` is `True` because the empty string is trivially segmentable.
- The answer we want is `dp[len(s)]`.

Defining the DP State

- For each end position `i`, look at every split point `j < i`.
- If `dp[j]` is `True` and the slice `s[j:i]` is a dictionary word, then `dp[i]` is reachable.
- Once we find one valid split we can stop scanning that `i`.

Filling the Table

- Time: `O(n^2)` for the nested loops, times the slice/hash cost.
- Space: `O(n)` for the `dp` array plus the word set.
- This comfortably handles the constraints for the Word Break problem.