# Solution For Word Break Ii

Problem Statement:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

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.

Solution:

The problem can be solved using a recursive approach. We start iterating over the input string and keep on adding characters to the currentWord until we find a match in the word dictionary. As soon as we find a match, we add the currentWord to the result and start with the next character. We keep on doing this until we reach the end of the string. However, this approach can get very slow if the input string is very large, or if multiple valid sentences can be formed.

To optimize this approach, we will use dynamic programming. We store a boolean array of size n+1, where n is the length of the input string. dp[i] represents whether the string upto the i-th index can be segmented into words from the dictionary or not. We also store a hashmap of size n+1, where the key represents the index upto which we have already found valid solutions, and the value is a list of possible sentences.

We start by initializing dp[0] to be true, since an empty string is always a valid solution. Then we iterate over the string s and check if s[j:i] (where j is any index upto i) is a valid word from the dictionary, and if dp[j] is also true (meaning the string upto index j can be segmented into words). If both these conditions are met, we set dp[i] to be true and add the substring s[j:i] to the list of possible sentences at index i in the hashmap.

Finally, we recursively traverse the hashmap, starting from the last index, and build the valid sentences.

Here’s the complete code:

class Solution {
public List wordBreak(String s, List wordDict) {
List result = new ArrayList<>();
int n = s.length();

``````    // Create a hashmap to store possible sentences upto each index
HashMap<Integer, List<String>> memo = new HashMap<>();
memo.put(n, new ArrayList<>());

// Create a boolean array to store whether the string upto an index can be segmented into words or not
boolean[] dp = new boolean[n+1];
dp[n] = true;

// Populate the boolean array and hashmap
for(int i=n-1; i>=0; i--) {
List<String> list = new ArrayList<>();
for(int j=i+1; j<=n; j++) {
if(dp[j] && wordDict.contains(s.substring(i,j))) {
dp[i] = true;
if(memo.containsKey(j)) {
for(String str: memo.get(j)) {
list.add(s.substring(i,j) + (str.equals("") ? "" : " ") + str);
}
}
}
}
memo.put(i, list);
}

// Build valid sentences using hashmap
return memo.get(0);
}
``````

}

Time Complexity: O(n^2 * wordDict.length), where n is the length of the input string. We iterate over each index in the string n times, and for each index, we iterate over all possible substrings. We also need to check whether a string is present in the word dictionary, which takes O(wordDict.length) time.

Space Complexity: O(n^2), for the hashmap and boolean array.

## Step by Step Implementation For Word Break Ii

```public class Solution {
public List wordBreak(String s, Set wordDict) {
List result = new ArrayList();
List list = new ArrayList();
wordBreakHelper(s, wordDict, result, list);
return result;
}

public void wordBreakHelper(String s, Set wordDict, List result, List list){
if(s.length() == 0){
StringBuilder sb = new StringBuilder();
for(String str : list){
sb.append(str);
sb.append(" ");
}
sb.deleteCharAt(sb.length()-1);
return;
}

for(int i = 1; i <= s.length(); i++){
String str = s.substring(0,i);
if(wordDict.contains(str)){
wordBreakHelper(s.substring(i), wordDict, result, list);
list.remove(list.size()-1);
}
}
}
}```
```class Solution:
# @param s: A string
# @param wordDict: A set of words.
# @return: All possible sentences.
def wordBreak(self, s, wordDict):
def dfs(s, wordDict, stringlist):
if self.check(s, wordDict):
if len(s) == 0: results.append(stringlist[1:])
for i in range(1, len(s)+1):
if s[:i] in wordDict:
dfs(s[i:], wordDict, stringlist+[s[:i]])

results = []
dfs(s, wordDict, [])
return results

def check(self, s, wordDict):
dp = [False for i in range(len(s)+1)]
dp[0] = True
for i in range(1, len(s)+1):
for k in range(i):
if dp[k] and s[k:i] in wordDict:
dp[i] = True
return dp[len(s)]```
```var wordBreak = function(s, wordDict) {
// create a map to store all the possible word breaks
// for a string (from the dictionary)
let map = new Map();

// create a set to store all the dictionary words
let set = new Set(wordDict);

// helper function to check if a string can be broken into
// dictionary words
let canBreak = function(str) {
// if the string is empty, then it can be broken
if (str.length === 0) {
return true;
}

// if we have already calculated the result for this string,
// then return the result from the map
if (map.has(str)) {
return map.get(str);
}

// iterate through the string
for (let i = 1; i <= str.length; i++) {
// get the substring from the start of the string to the current index
let prefix = str.substring(0, i);

// if the prefix is in the dictionary, then we can check if the
// remaining string can also be broken into dictionary words
if (set.has(prefix) && canBreak(str.substring(i))) {
// store the result in the map and return true
map.set(str, true);
return true;
}
}

// if we reach here, then it means that the string cannot be broken
// into dictionary words, so we store false in the map and return false
map.set(str, false);
return false;
}

// check if the input string can be broken into dictionary words
if (!canBreak(s)) {
return [];
}

// helper function to get all the possible word breaks for a string
let getBreaks = function(str) {
// if the string is empty, then return an empty array
if (str.length === 0) {
return [];
}

// if we have already calculated the result for this string,
// then return the result from the map
if (map.has(str)) {
return map.get(str);
}

// result array
let result = [];

// iterate through the string
for (let i = 1; i <= str.length; i++) {
// get the substring from the start of the string to the current index
let prefix = str.substring(0, i);

// if the prefix is in the dictionary, then we can check if the
// remaining string can also be broken into dictionary words
if (set.has(prefix)) {
// if the remaining string can be broken into dictionary words,
// then get all the possible word breaks for the remaining string
let suffixBreaks = getBreaks(str.substring(i));

// iterate through all the possible word breaks for the remaining string
for (let j = 0; j < suffixBreaks.length; j++) {
// add the prefix to the word break and add it to the result array
result.push(prefix + ' ' + suffixBreaks[j]);
}
}
}

// store the result in the map and return it
map.set(str, result);
return result;
}

// return all the possible word breaks for the input string
return getBreaks(s);
};```
```class Solution {
public:
// backtracking function to find all possible strings that can be formed
void findAllPossibleWords(string s, int index, unordered_set& wordDict, string& currentString, vector& allPossibleWords) {
// if we have reached the end of the string
if(index == s.length()) {
// add the current string to the list of all possible words
allPossibleWords.push_back(currentString);
// return from the function
return;
}

// iterate over all the remaining characters in the string
for(int i = index; i < s.length(); i++) {
// extract the substring from the current index to the current index + i
string substring = s.substr(index, i - index + 1);
// if the substring is present in the word dictionary
if(wordDict.find(substring) != wordDict.end()) {
// add the substring to the current string
currentString += substring + " ";
// call the backtracking function recursively for the remaining part of the string
findAllPossibleWords(s, i + 1, wordDict, currentString, allPossibleWords);
// remove the substring from the current string
currentString.erase(currentString.length() - substring.length() - 1);
}
}
}

vector wordBreak(string s, vector& wordDict) {
// create a set from the given word dictionary for faster lookup
unordered_set wordSet(wordDict.begin(), wordDict.end());
// create an empty vector to store all the possible words that can be formed
vector allPossibleWords;
// create an empty string to store the current word
string currentString = "";
// call the backtracking function to find all possible words
findAllPossibleWords(s, 0, wordSet, currentString, allPossibleWords);
// return the vector of all possible words
return allPossibleWords;
}
};```
```using System;
using System.Collections.Generic;

public class Solution {
public IList WordBreak(string s, IList wordDict) {
// create a list to store all the possible sentences
IList result = new List();
// create a set to store all the words in the dictionary
HashSet set = new HashSet(wordDict);
// create a two-dimensional array to store all the possible substrings
// that can be formed from the given string
bool[,] dp = new bool[s.Length, s.Length];

// fill up the dp array
for(int i = 0; i < s.Length; i++) {
for(int j = i; j < s.Length; j++) {
string substring = s.Substring(i, j - i + 1);
// if the substring is in the set, then it is a valid word
// and we can set the dp value to true
if(set.Contains(substring)) {
dp[i, j] = true;
}
// if the substring is not in the set, then check if it can be
// formed by concatenating two valid words
else {
for(int k = i; k < j; k++) {
if(dp[i, k] && dp[k + 1, j]) {
dp[i, j] = true;
break;
}
}
}
}
}

// now that we have the dp array filled up, we can use it to generate
// all the possible sentences
GenerateSentences(s, dp, 0, new List(), result);
return result;
}

// this function generates all the possible sentences by making use of the dp array
public void GenerateSentences(string s, bool[,] dp, int index, List current, IList result) {
// if we have reached the end of the string, then we have generated a sentence
if(index == s.Length) {
// convert the list of words into a string and add it to the result
}
// if we have not reached the end of the string, then keep generating sentences
else {
for(int i = index; i < s.Length; i++) {
// if the substring from index to i can be formed by concatenating
// valid words, then we can add it to the current sentence
if(dp[index, i]) {
string substring = s.Substring(index, i - index + 1);
// generate all the possible sentences by making use of the dp array
GenerateSentences(s, dp, i + 1, current, result);
// remove the word from the current sentence
current.RemoveAt(current.Count - 1);
}
}
}
}
}```

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]