Word Break II


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 breaksame 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)

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); Queue<Integer> queue = new LinkedList<>(); Queue<String> queueStr = new LinkedList<>(); List<String> list = new ArrayList<>(); queue.add(0); 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()) list.add(newStr); else { queueStr.add(newStr + " "); queue.add(end); } } } } } return list; }

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>(); postInds[n].add(n); 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; } inds.add(j); } 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()) { res.add(sb.toString()); 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); } } }