# Word Break II Leetcode Solution

In this post, we are going to solve the Word Break II Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

## Problem

Given a string `s` and a dictionary of strings `wordDict`, add spaces in `s` to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

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

Example 1:

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

Example 2:

```Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: Note that you are allowed to reuse a dictionary word.
```

Example 3:

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

Constraints:

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

Now, lets see the leetcode solution of Word Break II Leetcode Solution.

### Word Break II Leetcode Solution in Python

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

@functools.lru_cache(None)
def wordBreak(s: str) -> List[str]:
ans = []

# 1 <= len(prefix) < len(s)
for i in range(1, len(s)):
prefix = s[0:i]
suffix = s[i:]
if prefix in wordSet:
for word in wordBreak(suffix):
ans.append(prefix + ' ' + word)

# Contains whole string, so don't add any space
if s in wordSet:
ans.append(s)

return ans

return wordBreak(s)```

### Word Break II Leetcode Solutionin CPP

```class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet{begin(wordDict), end(wordDict)};
unordered_map<string, vector<string>> memo;
return wordBreak(s, wordSet, memo);
}

private:
vector<string> wordBreak(const string& s,
const unordered_set<string>& wordSet,
unordered_map<string, vector<string>>& memo) {
if (memo.count(s))
return memo[s];

vector<string> ans;

// 1 <= prefix.length() < s.length()
for (int i = 1; i < s.length(); ++i) {
const string& prefix = s.substr(0, i);
const string& suffix = s.substr(i);
if (wordSet.count(prefix))
for (const string& word : wordBreak(suffix, wordSet, memo))
ans.push_back(prefix + " " + word);
}

// Contains whole string, so don't add any space
if (wordSet.count(s))
ans.push_back(s);

return memo[s] = ans;
}
};```

### Word Break II Leetcode Solution in Java

```class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
Map<String, List<String>> memo = new HashMap<>();
return wordBreak(s, wordSet, memo);
}

private List<String> wordBreak(final String s, Set<String> wordSet,
Map<String, List<String>> memo) {
if (memo.containsKey(s))
return memo.get(s);

List<String> ans = new ArrayList<>();

// 1 <= prefix.length() < s.length()
for (int i = 1; i < s.length(); ++i) {
final String prefix = s.substring(0, i);
final String suffix = s.substring(i);
if (wordSet.contains(prefix))
for (final String word : wordBreak(suffix, wordSet, memo))
ans.add(prefix + " " + word);
}

// Contains whole string, so don't add any space
if (wordSet.contains(s))