Question
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"].
Stats
| Adjusted Difficulty | 5 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is a tough question. Standard DFS search would work, but we need to check ‘breakable’ first. Otherwise, I got TLE.
Check breakable is a easy DP, and we do not need to remove any elements from the dictionary. (Word ladder needs remove elements from dictionary, don’t confuse them).
Solution
Updated on July 4th, 2014. The DFS code actually standard, but keep in mind to check breakable first (using DP).
Code
DFS with pruning and DP breakable check, with the again-updated code on Sep 12th, 2014.
public List<String> wordBreak(String s, Set<String> dict) {
List<String> ans = new ArrayList<String>();
if (s == null || s.length() == 0 || dict == null) {
return ans;
} else if (!canBreak(s, dict)) {
return ans;
}
helper(ans, "", s, 0, dict);
return ans;
}
private void helper(List<String> ans, String str, String s, int pos, Set<String> dict) {
int len = s.length();
if (pos == len) {
ans.add(str.substring(1));
return;
}
for (int i = pos; i < len; i++) {
String sub = s.substring(pos, i + 1);
if (dict.contains(sub)) {
helper(ans, str + " " + sub, s, i + 1, dict);
}
}
}
public boolean canBreak(String s, Set<String> dict) {
if (s == null || s.length() == 0) {
return true;
}
int len = s.length();
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
if (!dp[j]) {
continue;
}
if (dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[len];
}