# LeetCode 139. Word Break

## Description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

Example 1:

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

Example 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.
```

Example 3:

```Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false```

## Explanation

We need to determine if s can be segmented into a space-separated sequence of one or more dictionary words.

We can introduce a state variable isWordBreak[i] to indicate whether the first iith characters of the input string is able to break into words that all in the dictionary.

Set isWordBreak to true, indicating that empty string ”” is also in the wordDict.

• isWordBreak[j] is used to indicate whether the first j characters of the input string is able to break into words that all in the dictionary
• Only when isWordBreak[j] = true（first j characters of the input string is word breakable) and s.substring(j, i) is also a word in the wordDict, first i characters of s can be word breakable.

## Java Solution

``````class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean[] isWordBreak = new boolean[s.length() + 1];

isWordBreak = true;

for (int i = 0; i < s.length() + 1; i++) {
for (int j = 0; j < i; j++) {
if (!isWordBreak[j]) {
continue;
}

if (wordDict.contains(s.substring(j, i))) {
isWordBreak[i] = true;
break;
}
}
}

return isWordBreak[s.length()];
}
}``````

## Python Solution

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

f = [False for i in range(len(s) + 1)]
f = True

for i in range(len(s)):
for j in range(i, len(s)):
if f[i] and s[i:j + 1] in wordDict:
f[j + 1] = True

return f[len(s)]``````
• Time Complexity: O(N^2)
• Space Complexity: O(N)

## 2 Thoughts to “LeetCode 139. Word Break”

1. Joy Chen says:

“isWordBreak==TRUE && s.substring(4,10) in WordDict”

In this statement, don’t we need to distinguish whether s.substring(5,10) is in WordDict or not?
So in the code,
if (wordDict.contains(s.substring(j+1, i))) {
isWordBreak[i] = true;
break;
}

2. Piyush says:

what will be the time complexity for the algorithm?