140 Word Break II – Hard
Problem:
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”].
Thoughts:
A easily modified version from Word Break I shown below is having Time Limit Exceeded issue when you submit. Probably this is because string manipulation is taking more time comparing just only keep a record of index.
Solutions:
easier to understand version
public class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> result = new LinkedList<String>();
if (s == null || s.length() == 0 || wordDict == null) {
return result;
}
HashMap<Integer, List<Integer>> pointers = new HashMap<Integer, List<Integer>>();
List<Integer> tmp = new LinkedList<Integer>();
tmp.add(-1);
pointers.put(-1, tmp);
for (int j = 0; j < s.length(); j ++) {
pointers.put(j, new LinkedList<Integer>());
for (int i = 0; i <= j; i ++) {
if (pointers.get(i - 1).size() > 0 && wordDict.contains(s.substring(i, j + 1))) {
pointers.get(j).add(i);
}
}
}
generate(s, result, s.length() - 1, pointers, "");
return result;
}
private void generate(String s, List<String> result, int index, HashMap<Integer, List<Integer>> pointers, String suffix) {
List<Integer> nexts = pointers.get(index);
if (pointers.size() == 0) {
return;
}
if (index == -1) {
result.add(suffix.substring(0, suffix.length() - 1));
return;
}
for (Integer next:nexts) {
generate(s, result, next - 1, pointers, s.substring(next, index + 1) + " " + suffix);
}
}
}
First version:
public class Solution {
private void search(int index, String s, List<Integer> path,
boolean[][] isWord, boolean[] possible,
List<String> result) {
if (!possible[index]) {
return;
}
if (index == s.length()) {
StringBuilder sb = new StringBuilder();
int lastIndex = 0;
for (int i = 0; i < path.size(); i++) {
sb.append(s.substring(lastIndex, path.get(i)));
if (i != path.size() - 1) sb.append(" ");
lastIndex = path.get(i);
}
result.add(sb.toString());
return;
}
for (int i = index; i < s.length(); i++) {
if (!isWord[index][i]) {
continue;
}
path.add(i + 1);
search(i + 1, s, path, isWord, possible, result);
path.remove(path.size() - 1);
}
}
public List<String> wordBreak(String s, Set<String> wordDict) {
ArrayList<String> result = new ArrayList<String>();
if (s.length() == 0) {
return result;
}
boolean[][] isWord = new boolean[s.length()][s.length()];
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
String word = s.substring(i, j + 1);
isWord[i][j] = wordDict.contains(word);
}
}
boolean[] possible = new boolean[s.length() + 1];
possible[s.length()] = true;
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
if (isWord[i][j] && possible[j + 1]) {
possible[i] = true;
break;
}
}
}
List<Integer> path = new ArrayList<Integer>();
search(0, s, path, isWord, possible, result);
return result;
}
}