# Word Break II Leetcode Solution

#### ByBrokenprogrammers

Dec 11, 2022

Hello Programmers, In this post you will know how 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.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.

## 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.

### Word Break II Leetcode Solutions 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 Solutionsin 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 Solutions 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))
memo.put(s, ans);
return ans;
}
}```

Note: This problem Word Break II is generated by Leetcode but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.