## 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:trueExplanation:Return true because`"leetcode"`

can be segmented as`"leet code"`

.

**Example 2:**

Input:s = "applepenapple", wordDict = ["apple", "pen"]Output:trueExplanation: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[0] 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[0] = 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[0] = 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)

Hi Guys

I made a small video explaining the recursion and DP approach, please check this out

https://www.youtube.com/watch?v=gjmfFd0Pmh4&t=15s

I found that solution is very popular and helpful : https://www.youtube.com/watch?v=_JYE_M3uD-Y

“isWordBreak[4]==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;

}

what will be the time complexity for the algorithm?