140. Word Break II
You are given a lowercase string s and a list of dictionary words. Insert spaces into s to break it into a sentence in which every piece is a dictionary word — the same word may be reused freely. Return every possible sentence as a list of strings, sorted in ascending lexicographic order. If s cannot be segmented at all, return an empty list (the judge prints -1 for that case).
s is short (at most 20 characters), so an exhaustive search is expected — the craft is in memoizing shared suffixes and cutting dead branches early.
Example 1:
Input: s = "sunflowerpot", words = ["sun", "flower", "pot", "sunflower", "flow", "erpot"]
Output: ["sun flow erpot", "sun flower pot", "sunflower pot"]
Explanation: Three segmentations exist. Sorted as plain strings they read: "sun flow erpot", "sun flower pot", "sunflower pot".
Example 2:
Input: s = "aaa", words = ["a", "aa"]
Output: ["a a a", "a aa", "aa a"]
Explanation: Reusing words is allowed, and different orderings of the same pieces are distinct sentences.
Example 3:
Input: s = "dogcatx", words = ["dog", "cat"]
Output: []
Explanation: "dog" + "cat" covers the first six characters but nothing matches the trailing "x", so there is no valid sentence and the answer is the empty list.
Constraints:
- 1 ≤ s.length ≤ 20
- 1 ≤ words.length ≤ 100
- 1 ≤ words[i].length ≤ 10
- s and every word consist of lowercase English letters only
- All dictionary words are distinct.
Hints:
This is Word Break with the answer set materialized: instead of a boolean per position, you need the actual sentences. Depth-first search naturally builds one sentence per root-to-leaf path.
Backtrack over cut points: at position i, try every j such that s[i..j) is a dictionary word, recurse from j, and pop the piece afterward. Bound j by the longest word length.
Different prefixes can leave the same suffix, and you would re-enumerate its sentences each time. Memoize start index → list of sentences for that suffix, so each suffix is expanded once.
Remember the canonical form: sort the finished list of sentences before returning it.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "sunflowerpot", words = ["sun", "flower", "pot", "sunflower", "flow", "erpot"]
Expected output: ["sun flow erpot", "sun flower pot", "sunflower pot"]