648. Replace Words Medium

1/**
2 * [648] Replace Words
3 *
4 * In English, we have a concept called root, which can be followed by some other word to form another longer word - let's call this word successor. For example, when the root "an" is followed by the successor word "other", we can form a new word "another".
5 * Given a dictionary consisting of many roots and a sentence consisting of words separated by spaces, replace all the successors in the sentence with the root forming it. If a successor can be replaced by more than one root, replace it with the root that has the shortest length.
6 * Return the sentence after the replacement.
7 *  
8 * Example 1:
9 * 
10 * Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
11 * Output: "the cat was rat by the bat"
12 * 
13 * Example 2:
14 * 
15 * Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
16 * Output: "a a b c"
17 * 
18 *  
19 * Constraints:
20 * 
21 * 	1 <= dictionary.length <= 1000
22 * 	1 <= dictionary[i].length <= 100
23 * 	dictionary[i] consists of only lower-case letters.
24 * 	1 <= sentence.length <= 10^6
25 * 	sentence consists of only lower-case letters and spaces.
26 * 	The number of words in sentence is in the range [1, 1000]
27 * 	The length of each word in sentence is in the range [1, 1000]
28 * 	Every two consecutive words in sentence will be separated by exactly one space.
29 * 	sentence does not have leading or trailing spaces.
30 * 
31 */
32pub struct Solution {}
33
34// problem: https://leetcode.com/problems/replace-words/
35// discuss: https://leetcode.com/problems/replace-words/discuss/?currentPage=1&orderBy=most_votes&query=
36
37// submission codes start here
38
39impl Solution {
40    pub fn replace_words(dictionary: Vec<String>, sentence: String) -> String {
41        String::new()
42    }
43}
44
45// submission codes end
46
47#[cfg(test)]
48mod tests {
49    use super::*;
50
51    #[test]
52    fn test_648() {
53    }
54}
55