Algorithm {Word Break II}

Today we will work on hard task Word Break II. Why this task is hard? I can say, here, during resolving this problem, you will and you should use a few techniques.

First one traversing method called DFS (or BFS), second is Dynamic programming, third is some combining and tricks 🙂 to pass tests on leetcode.

OK, try to read task description :

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

We can see, that we have some dictionary and first idea will be about traversing through dictionary, but it will be mistake. For example you have simple input string like catsanddog and dictionary with 1 billion of words, what is the complexity will be ? Yes, O(N^2) where is N equals to 1 billion. And generally I do not think that complexity of our solution should be dependent from dictionary size!

What we can todo, try to analyse … We can run through all letters in input word and try to find all words from our dic, if found put to storage (DP) end index of word (or start index) depend to the direction of string traversing. I am storing not just indexes but word too, to speed up our solution.

OK, at the end you will have something like that:

import java.util.*;
 
/**
* catsanddog
*
* @author 
*/
public class WordBreakII {
public List<String> wordBreak(String s, Set<String> dict) {
List<String> result = new ArrayList<String>();
int length = s.length() + 1;
List<List<Integer>> mask = new ArrayList<List<Integer>>(length);
for (int i = 0; i < length; i++) {
mask.add(new ArrayList<Integer>());
}
 
for (int i = 0; i < length; i++) {
for (int j = i; j < length; j++) {
String word = s.substring(i, j);
if (dict.contains(word)) {
mask.get(i).add(j);
}
}
}
buildResult(mask, 0, result, "", s);
return result;
}
 
private void buildResult(List<List<Integer>> mask, int index, List<String> result, String val, String src) {
if (index == src.length()) {
result.add(val.trim());
return;
}
 
for (Integer end : mask.get(index)) {
String word = src.substring(index, end);
if (index == 0) {
val = word+ " ";
} else {
val += word + " ";
}
buildResult(mask, end, result, val, src);
}
}
}

But you will get Time Limit Exceeded exception. Generally this solution is good, but we have problems in analysing words like that :

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

if (index == src.length()) {
result.add(val.trim());
return;
}

mask.get(i).add(j);

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
 
/**
* catsanddog
*
* @author 
*/
public class WordBreakII {
public List<String> wordBreak(String s, Set<String> dict) {
List<String> result = new ArrayList<String>();
int length = s.length() + 1;
List<List<Pair>> mask = new ArrayList<List<Pair>>(length);
for (int i = 0; i < length; i++) {
mask.add(new ArrayList<Pair>());
}
for (int i = 0; i < length; i++) {
for (int j = i; j < length; j++) {
String word = s.substring(i, j);
 
if (dict.contains(word)) {
mask.get(j).add(new Pair(i, word));
}
 
}
}
if (mask.get(mask.size() - 1).size() > 0)
buildResult(mask, mask.size() - 1, result, "");
return result;
}
 
private void buildResult(List<List<Pair>> mask, int index, List<String> result, String val) {
if (index == 0) {
result.add(val.trim());
return;
}
 
for (Pair pair : mask.get(index)) {
 
String word = pair.val;
val = word + " " + val;
 
buildResult(mask, pair.key, result, val);
 
val = removeCurrentWord(val);
}
}
 
private String removeCurrentWord(String val) {
int i = val.indexOf(" ");
if (i >= 0)
val = val.substring(i + 1);
return val;
}
 
private class Pair {
public int key;
public String val;
 
public Pair(int key, String val) {
this.key = key;
this.val = val;
}
}

}

private class Pair {
public int key;
public String val;
 
public Pair(int key, String val) {
this.key = key;
this.val = val;
}
}

and storing end – start indexes, it means storing in end bucket start index (and word)
mask.get(j).add(new Pair(i, word));

so, before build result I am checking if there are some solutions, I am mean if some DFS traversing way ended in last bucket.
if (mask.get(mask.size() - 1).size() > 0)