617. Every Way to Split Words
A subtitle file lost every space, leaving one long lowercase string s. A list dictionary holds the words the speaker is known to use. A word from the list may be used any number of times.
Return every sentence that can be made by inserting single spaces into s so that each resulting word is in dictionary. Every character of s must be used, in order. Sentences may be returned in any order. If s cannot be split, return an empty array. It is guaranteed that at most 200 sentences exist for each input.
Example 1
- Input:
- s = "brightfuture"dictionary = ["bright","future","brig","ht","fut","ure"]
- Output:
- ["brig ht fut ure","brig ht future","bright fut ure","bright future"]
- Explanation:
Both
brightandbrig htcan start the sentence, and bothfutureandfut urecan finish it, so there are 2 * 2 = 4 sentences.
Example 2
- Input:
- s = "moonlight", dictionary = ["moon","light","night"]
- Output:
- ["moon light"]
- Explanation:
The only split is
moon light.
Example 3
- Input:
- s = "tomato", dictionary = ["to","ma","tom"]
- Output:
- ["to ma to"]
- Explanation:
The only split is
to ma to: starting withtomleavesato, which cannot be split.
Constraints
- 1 ≤
s.length≤ 20 - 1 ≤
dictionary.length≤ 12, each word has 1 to 10 lowercase letters - All words in
dictionaryare different. - At most 200 sentences exist for each input.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(n^2 + answer size)
- Space
- O(n)