> For the complete documentation index, see [llms.txt](https://www.vjssn.dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://www.vjssn.dev/practice/24-06-06/lc139-word-break.md).

# LC139 - Word Break

## Problem

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

#### Sample 1

**Input:** s = "leetcode", wordDict = \["leet","code"]

**Output:** true

**Explanation:** Return true because "leetcode" can be segmented as "leet code".

#### Sample 2

**Input:** s = "applepenapple", wordDict = \["apple","pen"]

**Output:** true

**Explanation:** Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

## Solution

### Dynamic Programming

Break into the subproblem of segmenting substrings into a sequence of words. Time complexity of this solution is $$O(n^2)$$ while space complexity is $$O(s)$$ due to the use of an array that is the length of the string.

```python
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
	arr = [False] * (len(s) + 1)
	# base case is always True, empty string always can be segmented
	arr[0] = True

	for i in range(1, len(s) + 1):
		# true if any is true
		for j in range(i):
			if arr[j] and s[j:i] in wordDict:
				arr[i] = True
				break
	return arr[-1]
```