## Algorithm

Problem Name: 140. Word Break II

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.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
char **p;
int sz;
int n;
} res_t;
typedef struct {
char *b;
int sz;
int n;
} buff_t;
void add2res(res_t *res, char *str) {
if (res->sz == res->n) {
res->sz *= 2;
res->p = realloc(res->p, res->sz * sizeof(char *));
//assert(res->p);
}
res->p[res->n ++] = str;
}
void add2buff(buff_t *buff, int n, char *s, int l) {
buff->n = n;
if (buff->sz  < = buff->n + l + 2) {
buff->sz *= 2 + l + 2;
buff->b = realloc(buff->b, buff->sz * sizeof(char));
//assert(buff->b);
}
strncpy(&buff->b[buff->n], s, l);
buff->n += l;
buff->b[buff->n] = ' ';
buff->n ++;
}
int *newvec() {
int *vec = malloc(12 * sizeof(int));
//assert(vec);
vec[0] = 12;
vec[1] = 0;
return vec;
}
void add2vec(int *vec, int i) {
if (vec[0] == vec[1]) {
vec[0] *= 2;
vec = realloc(vec, vec[0] * sizeof(int));
//assert(vec);
}
vec[2 + vec[1] ++] = i;
}
void bt(res_t *res, buff_t *buff, char *s, int **dp, int start, int end) {
int i, k, n, *vec;

if (start == end) {
buff->b[-- buff->n] = 0;
return;
}

n = buff->n;

vec = dp[start];
for (i = 0; i  <  vec[1]; i ++) {
k = vec[2 + i];
add2buff(buff, n, &s[start], k - start);
bt(res, buff, s, dp, k, end);
}
}
char** wordBreak(char* s, char** wordDict, int wordDictSize, int* returnSize) {
res_t res;
buff_t buff;

int *wsz, **dp, *vec;
int len, i, j, k;

res.sz = 10;
res.n = 0;
res.p = malloc(res.sz * sizeof(char *));
//assert(res.p);

wsz = calloc(wordDictSize, sizeof(int));
len = strlen(s);
dp = calloc(len + 1, sizeof(int *));
//assert(dp && used && len);

buff.sz = 100;
buff.n = 0;
buff.b = malloc(buff.sz * sizeof(char));
//assert(buff.b);

for (i = 0; i  <  wordDictSize; i ++) {
wsz[i] = strlen(wordDict[i]);
}

dp[0] = newvec();
for (i = 0; i  <  len; i ++) {
if (dp[i]) {  // a valid point to cut
for (j = 0; j  <  wordDictSize; j ++) {
if (!strncmp(&s[i], wordDict[j], wsz[j])) {
k = i + wsz[j];
if (!dp[k]) dp[k] = newvec();
}
}
}
}

if (dp[len]) {
bt(&res, &buff, s, dp, 0, len);
}

free(wsz);
for (i = 1; i  < = len; i ++) {
if (dp[i]) free(dp[i]);
}
free(dp);
free(buff.b);

*returnSize = res.n;

return res.p;
}
``````
Copy The Code &

Input

cmd
s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]

Output

cmd
["cats and dog","cat sand dog"]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
Map();
public List wordBreak(String s, List  wordDict) {
Set set = new HashSet<>(wordDict);
return helper(s, set, 0);
}

private List < String> helper(String s, Set set, int start) {
if (map.containsKey(start)) {
return map.get(start);
}

List ans = new ArrayList <>();
if (start == s.length()) {
}
for (int i = start + 1; i  < = s.length(); i++) {
if (set.contains(s.substring(start, i))) {
List list = helper(s, set, i);
for (String word : list) {
ans.add(s.substring(start, i) + (word.equals("") ? "" : " ") + word);
}
}
}

map.put(start, ans);
return ans;
}
}
``````
Copy The Code &

Input

cmd
s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]

Output

cmd
["cats and dog","cat sand dog"]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const wordBreak = function(s, wordDict) {
const set = new Set(wordDict)
const map = new Map()
return helper(s, 0, set, map)
};

function helper(str, idx, set, map) {
if(idx === str.length) return []
if(map.has(idx)) return map.get(idx)
const res = []
for(let i = idx; i < str.length; i++) {
const tmp = str.slice(idx, i + 1)
if(set.has(tmp)) {
const arr = helper(str, i + 1, set, map)
if(i === str.length - 1) res.push(tmp)
for(let item of arr) {
res.push(`\${tmp} \${item}`)
}
}
}
map.set(idx, res>
return res
}
``````
Copy The Code &

Input

cmd
s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]

Output

cmd
["pine apple pen apple","pineapple pen apple","pine applepen apple"]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def wordBreak(self, s, wordDict):
def breakable():
rightmosts = [0]
for i in range(1, len(s) + 1):
for last_index in rightmosts:
if s[last_index:i] in words:
rightmosts.append(i)
if i == len(s):
return True
break
return False
q, res, words = [("", 0)], [], set(wordDict)
if breakable():
for j in range(1, len(s) + 1):
new = q[:]
for seq, i in q:
if s[i:j] in words:
if j == len(s):
res.append(seq and seq + " " + s[i:j] or s[i:j])
else:
new.append((seq and seq + " " + s[i:j] or s[i:j], j))
q = new
return res
``````
Copy The Code &

Input

cmd
s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]

Output

cmd
["pine apple pen apple","pineapple pen apple","pine applepen apple"]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _0140_WordBreakII
{
public IList < string> WordBreak(string s, IList wordDict)
{
var set = new HashSet(wordDict);
var cache = new Dictionary DFS(string s, HashSet set, Dictionary();
if (set.Contains(s))
{
}

for (int i = 1; i  <  s.Length; i++)
{
var str = s.Substring(i);
if (set.Contains(str))
{
var prevResults = DFS(s.Substring(0, i), set, cache);
foreach (var prev in prevResults)
result.Add(prev + " " + str);
}
}

cache[s] = result;
return result;
}
}
}
``````
Copy The Code &

Input

cmd
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

Output

cmd
[]