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 <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10sandwordDict[i]consist of only lowercase English letters.- All the strings of
wordDictare 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;
add2res(res, strdup(buff->b));
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];
add2vec(dp[i], k);
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;
}
Input
s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output
["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()) {
ans.add("");
}
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;
}
}
Input
s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
Output
["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
}
Input
s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output
["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
Input
s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output
["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))
{
result.Add(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;
}
}
}
Input
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output
[]