# Leetcode Word Break II problem solution

In this Leetcode Word Break II problem solution we have 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.

## Problem solution in Python.

```class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
res = []
self.wordDict = set(wordDict)
self.dfs(s, [], res)
return res
def dfs(self, s, path, res):
if not s:
res.append(" ".join(path))
return

for i in range(len(s)):
if s[:i+1] in self.wordDict:
self.dfs(s[i+1:], path+[s[:i+1]], res)
```

## Problem solution in Java.

```public List<String> wordBreak(String s, Set<String> wordDict) {
return DFS(s, wordDict, new HashMap<String, LinkedList<String>>());
}

List<String> DFS(String s, Set<String> wordDict, HashMap<String, LinkedList<String>>map) {
if (map.containsKey(s))
return map.get(s);

if (s.length() == 0) {
return res;
}
for (String word : wordDict) {
if (s.startsWith(word)) {
List<String>sublist = DFS(s.substring(word.length()), wordDict, map);
for (String sub : sublist)
res.add(word + (sub.isEmpty() ? "" : " ") + sub);
}
}
map.put(s, res);
return res;
}
```

## Problem solution in C++.

```class Solution
{
public:
void helper(string &s,string &curr,vector<string>&v,int index,unordered_set<string>&dict)
{
if(index==s.length())
{
curr.erase(curr.begin()+curr.length()-1);
v.push_back(curr);
return;
}
string tmp="";
for(int i=index;i<s.length();i++)
{
tmp.push_back(s[i]);
if(dict.find(tmp)!=dict.end())
{
string aux=curr;
curr+=(tmp+" ");
helper(s,curr,v,i+1,dict);
curr=aux;
}
}
}
vector<string> wordBreak(string s, vector<string>& wordDict)
{
unordered_set<string>dict(wordDict.begin(),wordDict.end());
vector<string>v;
string curr="";
helper(s,curr,v,0,dict);
return v;
}
};
```