- 23.3%

https://leetcode.com/problems/word-break-ii/

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

1 | For example, given |

UPDATE (2017/1/4):

The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

还需要思考

方法一:

https://discuss.leetcode.com/topic/12997/11ms-c-solution-concise

11ms C++ solution (concise)

1 | class Solution { |

方法二：

https://discuss.leetcode.com/topic/35762/9-lines-python-10-lines-c

9 lines Python, 10 lines C++

1 | vector<string> wordBreak(string s, unordered_set<string>& wordDict) { |

方法三：

我的代码实现：

超时了

“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa”

[“a”,”aa”,”aaa”,”aaaa”,”aaaaa”,”aaaaaa”,”aaaaaaa”,”aaaaaaaa”,”aaaaaaaaa”,”aaaaaaaaaa”]

1 | class Solution { |

#### python

https://discuss.leetcode.com/topic/35762/9-lines-python-10-lines-c

9 lines Python, 10 lines C++

1 | def wordBreak(self, s, wordDict): |

#### java

https://discuss.leetcode.com/topic/27855/my-concise-java-solution-based-on-memorized-dfs

My concise JAVA solution based on memorized DFS

18ms, 34.39%, Jan.13 2017

Explanation

Using DFS directly will lead to TLE, so I just used HashMap to save the previous results to prune duplicated branches, as the following:

1 | public class Solution { |

Brilliant idea, also can be simplified like this.

1 | public class Solution { |

https://discuss.leetcode.com/topic/9837/my-concise-answer

My concise answer.

1 | public class Solution { |

https://discuss.leetcode.com/topic/8178/slightly-modified-dp-java-solution

Slightly modified DP Java solution

Hi guys!

There’s a lot of concern in other posts about “aaaa…aab” test case that causes TLE when we run through our string not in reverse but from start to end. I’ve thought a bit on how to add a tiny modification and make just the whole thing more effective, not only pass the TLE case.

The approach is the same as before: we loop through all possible prefixes checking if it in the dictionary and caching the results.

But just before jumping into recursion we could also check that the right reminder has a prefix from the dictionary, because if it hasn’t then there’s no sense in splitting the reminder into sub-strings. It’s just a linear check, which I think also could be optimized with some caching but even without optimization the solution is accepted. And also the code looks quite understandable.

1 | public class Solution { |

https://discuss.leetcode.com/topic/39833/java-6ms-simple-solution-beating-88

Java 6ms simple solution beating 88%

1 | public class Solution { |

https://discuss.leetcode.com/topic/3495/my-dp-solution-in-java

My DP solution in JAVA

Basically my idea is the following:

- Scan the the string from the tail
- Build possible solution for the current index based on DP results
- Return the solution when index==0

1 | public class Solution { |

Java DP+DFS, Memoization+DFS, and DP Pruning Solutions with Analysis

I’ve been struggling with this problem for a long time, and I’d love to share three different strategies I have tried to solve it. All of them are ACed.

Method 1: DP + DFS. Very similar to Word Break I, but instead of using a boolean dp array, I used an array of Lists to maintain all of the valid start positions for every end position. Then just do classic backtracking to find all solutions. The time complexity is O(n*m) + O(n * number of solutions), where n is the length of the input string, m is the length of the longest word in the dictionary. The run time was 6ms. It is very efficient because DP is used to find out all the valid answers, and no time is wasted on doing the backtracking.

1 | public List<String> wordBreak(String s, Set<String> wordDict) { |

Method 2: Memoization + Backtracking. Before I came up with Method 1, I also tried using a HashMap to memoize all the possible strings that can be formed starting from index i. I referred to this post from @Pixel_

The time complexity is O(len(wordDict) ^ len(s / minWordLenInDict)) as @Pixel_ mentioned. The space complexity would be larger than other methods though. Here is my code:

1 | public List<String> wordBreak(String s, Set<String> wordDict) { |

Method 3: DP Prunning + Backtracking. My very first solution is like this: using a boolean array to memoize whether a substring starting from position i to the end is breakable. This works well for worst cases like: s = “aaaaaaaaaaaab”, dict = [“a”, “aa”, “aaa”, “aaaa”]. However, for cases like: s = “aaaaaaaaaaaaa”, dict = [“a”, “aa”, “aaa”, “aaaa”], the time complexity is still O(2^n). Here is the code:

1 | public List<String> wordBreak(String s, Set<String> wordDict) { |