# Word Break II

• Why DP is time limited?

• Where to get the tutorial about DP

• Why is DP method Time Limit Exceeded while it is still O(n3)？

• For the recursive approach, why add "" if (start == s.length())?

• For the recursive approach, why add "" if (start == s.length())? nvm, I got it.

• I can't agree with the complexity analysis of the brute force search. You can think the brute force search is to try all the options whether to insert a space at position i.
So the total options to search is 2^n, so the time complexity should be O(2^n) n is the length of the sentence to break

same thing, for the space complexity, it's same all those 2^n can be a valid break, so the space complexity is also O(2^n)

• @vinod23

Can you help to write code in iterative manner for Approach #2 Recursion with memoization [Accepted] ?

• This problem is quite frustrating. Why is it that if the input is:
"abcd"
["a","abc","b","cd"]
Expected:
["a b cd"]

but if the input is:
"a"
["a"]
Expected:
["a"]
?

Why isn't "abc" an acceptable sentence in the first test case?

• I don't really agree that the time complexity of approach 2 is O(n^3). Considering the worst case string = "aaaaaaa" and every prefix of the string is in the dictionary, the list of string the algorithm desires is basically generating all combinations of the space existence between any two characters. So it is at least O(2^n) because you need at least 2^n strings in the result list.

• Another solution is to use BFS from Word Break I. Exact same code, just modifying a little bit.
First, get rid of visited[] array. Second, and another queue, this queue will go along with the normal index queue to store the substrings at each level. At each level, a substring is created by concatenating the found string at the current level with the string from previous level. Although TLE (have to add a word breakable check to make it acceptable), it's still a learning experience.

``````public List<String> wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet(wordDict);
List<String> list = new ArrayList<>();

queueStr.offer("");

while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String currentStr = queueStr.poll();
int start = queue.poll();
for (int end = start + 1; end <= s.length(); end++) {
String subStr = s.substring(start, end);
if (wordDictSet.contains(subStr)) {
String newStr = currentStr + subStr;
if (end == s.length())
else {
}
}
}
}
}
return list;
}
``````

• @MitchellHe

Now I find answers to my own question. The bottom up DP solution is good solution only when we know where to start and which branches are valuable to global result. For this problem, an memorization search would be a good answer as we would only spend time on where in need. In detail, The reason that DP method Time Limit Exceeded is that the method computed too much time in invalid branches. There are many intermediate lists which will not construct final result. At the time of computing these lists, we did not know whether it will be included in final result, as a result, my suggestion is that, if we really want to solve this problem using DP, instead of spending O(k) time, where k is the length of the intermediate list, we could have just spend o(1) time by only storing the previous one degree indexes based on which we could rebuild the result string list, instead of computing the result string list. This is quite similar to the problem Word Ladder II.

Here is an amended accepted DP solution.

``````class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> res = new ArrayList<>();
if (s == null || wordDict == null || s.length() == 0 || wordDict.size() == 0) {
return res;
}
Set<String> dict = new HashSet<>(wordDict);
int n = s.length();
Set<Integer>[] postInds = new Set[n + 1]; //postInds[i] = set of next valid indexes after ith char in s.
postInds[n] = new HashSet<Integer>();
for (int i = n - 1; i >= 0; --i) {
Set<Integer> inds = new HashSet<>();
for (int j = i + 1; j <= n; ++j) {
if (postInds[j].size() == 0) {
continue;
}

String word = s.substring(i, j);
if (!dict.contains(word)) {
continue;
}
}
postInds[i] = inds;
}
buildRes(s, 0, new StringBuilder(), res, postInds);
return res;
}

private void buildRes(String s, int ind, StringBuilder sb, List<String> res, Set<Integer>[] postInds) {
if (ind == s.length()) {
return;
}
int size = sb.length();
for (int nextInd : postInds[ind]) {
String word = s.substring(ind, nextInd);
if (size > 0) {
sb.append(" ");
}
sb.append(word);
buildRes(s, nextInd, sb, res, postInds);
sb.setLength(size);
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.