Work Break
This is a dynamic programing problem. A string s
can be split into words if and only if
s[i..end]
is in dictionary and s[start..i]
is able to be split into words.
public class WordBreak {
public boolean wordBreak(String s, Set<String> wordDict) {
int len = 0;
for (String word: wordDict) {
len = Math.max(len, word.length());
}
boolean[] canSplit = new boolean[s.length() + 1];
canSplit[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = i - 1; j >= i - len && j >= 0; j--) {
if (canSplit[j]) {
if(wordDict.contains(s.substring(j, i))) {
canSplit[i] = true;
break;
}
}
}
}
return canSplit[s.length()];
}
}
Reserve words
In Word Break II, you are asked to return all possible
splits. The time cost will be a bit high if we do that like what we do above.
To avoid iterating over each position in string s
we can use a recursive way to get result
and add a cache HashMap
to save intermediate results.
We can either start from the begining or from the end. Following code shows the latter.
public class WordBreakII {
private List<String> wordBreak(String s, Set<String> wordDict, int len, int pos, HashMap<Integer, List<String>> cache) {
if (cache.containsKey(pos)) return cache.get(pos);
ArrayList<String> res = new ArrayList<String>();
if (pos == 0) {
res.add("");
cache.put(0, res);
return res;
}
for (int i = pos - 1; i >= 0 && i >= pos - len; i--) {
String word = s.substring(i, pos);
if (wordDict.contains(word)) {
List<String> sub = wordBreak(s, wordDict, len, i, cache);
for (String w: sub) {
if (w.isEmpty()) res.add(word);
else res.add(w + " " + word);
}
}
}
cache.put(pos, res);
return res;
}
public List<String> wordBreak(String s, Set<String> wordDict) {
int len = 0;
for(String w: wordDict) len = Math.max(len, w.length());
HashMap<Integer, List<String>> cache = new HashMap<Integer, List<String>>();
return wordBreak(s, wordDict, len, s.length(), cache);
}
}