# Word Break II LeetCode Solution

Here, We see Word Break II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

# List of all LeetCode Solution

## Problem Statement

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: []

## Word Break II LeetCode SolutionC++

``````class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict)
{
int max_len = 0;
unordered_set<string> dict;
for(string& str : wordDict)
{
dict.insert(str);
max_len = max(max_len, (int)str.length());
}
unordered_map<int, vector<string>> mp;
return break_word(s, 0, dict, max_len, mp);
}

protected:
vector<string> break_word(  const string& s, int n, unordered_set<string>& dict,
int max_len, unordered_map<int, vector<string>>& mp)
{
if(mp.count(n)) return mp[n];
string str;
for(int i = n; i < s.length() && str.length() <= max_len; ++i)
{
str += s[i];
if(dict.count(str))
{
if(i == s.length()-1)
mp[n].push_back(str);
else
{
vector<string> vs = break_word(s, i+1, dict, max_len, mp);
for(auto& a : vs) mp[n].push_back(str + " " + a);
}
}
}
return mp[n];
}
};```Code language: PHP (php)```

## Word Break II LeetCode SolutionJava

``````class Solution {
private void helper(String s, int i, Set<String> dict, List<String> cur, List<String> res) {
if (i == s.length()) {
if (cur.size() > 0) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < cur.size(); j++) {
if (j > 0) {
sb.append(' ');
}
sb.append(cur.get(j));
}
}
return;
}
for (int j = i+1; j <= s.length(); j++) {
if (dict.contains(s.substring(i, j))) {
helper(s, j, dict, cur, res);
cur.remove(cur.size() - 1);
}
}
}
public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> dict = new HashSet<>(wordDict);
List<String> res = new ArrayList<>();
List<String> cur = new ArrayList<>();
helper(s, 0, dict, cur, res);
return res;
}
}```Code language: JavaScript (javascript)```

## Word Break II SolutionJavaScript

``````var wordBreak = function(s, wordDict) {
const memo = new Map();
function run(str) {
if(memo.has(str)) return memo.get(str);
if(!str.length) return [];
const result = [];
for(let word of wordDict) {
if(str.startsWith(word)) {
const next = str.slice(word.length);
const paths = run(next);
if(!paths.length && !next.length) result.push(word);
result.push(...paths.map(rest => word + ' ' + rest));
}
}
memo.set(str, result);
return result;
}
return run(s);
};```Code language: JavaScript (javascript)```

## Word Break II SolutionPython

``````class Solution(object):
def wordBreak(self, s, wordDict):
return self.helper(s, wordDict, {})
def helper(self, s, wordDict, memo):
if s in memo: return memo[s]
if not s: return []
res = []
for word in wordDict:
if not s.startswith(word):
continue
if len(word) == len(s):
res.append(word)
else:
resultOfTheRest = self.helper(s[len(word):], wordDict, memo)
for item in resultOfTheRest:
item = word + ' ' + item
res.append(item)
memo[s] = res
return res``````
Scroll to Top