Word Break II
Hard · backtracking
You are given a string s of lower-case letters that has had all its spaces removed, and a list word_dict of allowed words. Put spaces back into s to make a sentence: a sequence of allowed words, separated by single spaces, that reads as s again when the spaces are taken out. Every word of word_dict may be used as many times as you like.
Return every different sentence that can be made. Return them in ascending dictionary order (compare the sentences as plain strings, character by character; a space comes before every letter). If s cannot be split into allowed words at all, return an empty list.
Examples
Example 1
Input: s = "sunsetwalk", word_dict = ["sun", "set", "sunset", "walk", "wal", "k"]
Output: ["sun set wal k", "sun set walk", "sunset wal k", "sunset walk"]
"sunset" can be one word or two, and "walk" can be one word or "wal" followed by "k".
Example 2
Input: s = "ababa", word_dict = ["ab", "aba", "ba", "a"]
Output: ["a ba ba", "ab a ba", "ab ab a", "ab aba", "aba ba"]
Five different ways to cut the string, listed in dictionary order.
Example 3
Input: s = "moonlight", word_dict = ["moon", "lit"]
Output: []
No cut of the string uses only allowed words.
Constraints
- 1 <= len(s) <= 20
- 1 <= len(word_dict) <= 20
- 1 <= len(word_dict[i]) <= 10
- s and every word contain only lower-case letters 'a' to 'z'
- All the words in word_dict are different