140. Word Break II Hard

1/**
2 * [140] Word Break II
3 *
4 * Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
5 * Note that the same word in the dictionary may be reused multiple times in the segmentation.
6 *  
7 * Example 1:
8 * 
9 * Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
10 * Output: ["cats and dog","cat sand dog"]
11 * 
12 * Example 2:
13 * 
14 * Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
15 * Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
16 * Explanation: Note that you are allowed to reuse a dictionary word.
17 * 
18 * Example 3:
19 * 
20 * Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
21 * Output: []
22 * 
23 *  
24 * Constraints:
25 * 
26 * 	1 <= s.length <= 20
27 * 	1 <= wordDict.length <= 1000
28 * 	1 <= wordDict[i].length <= 10
29 * 	s and wordDict[i] consist of only lowercase English letters.
30 * 	All the strings of wordDict are unique.
31 * 
32 */
33pub struct Solution {}
34
35// problem: https://leetcode.com/problems/word-break-ii/
36// discuss: https://leetcode.com/problems/word-break-ii/discuss/?currentPage=1&orderBy=most_votes&query=
37
38// submission codes start here
39
40impl Solution {
41    pub fn word_break(s: String, word_dict: Vec<String>) -> Vec<String> {
42        vec![]
43    }
44}
45
46// submission codes end
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51
52    #[test]
53    fn test_140() {
54    }
55}
56