## 648. Replace Words

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"`.

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.

Return the `sentence` after the replacement.

Example 1:

```Input: dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
```

Example 2:

```Input: dictionary = ["a","b","c"], sentence = "aadsfasf absbs bbab cadsfafs"
Output: "a a b c"
```

Example 3:

```Input: dictionary = ["a", "aa", "aaa", "aaaa"], sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa"
Output: "a a a a a a a a bbb baba a"
```

Example 4:

```Input: dictionary = ["catt","cat","bat","rat"], sentence = "the cattle was rattled by the battery"
Output: "the cat was rat by the bat"
```

Example 5:

```Input: dictionary = ["ac","ab"], sentence = "it is abnormal that this solution is accepted"
Output: "it is ab that this solution is ac"
```

Constraints:

• `1 <= dictionary.length <= 1000`
• `1 <= dictionary[i].length <= 100`
• `dictionary[i]` consists of only lower-case letters.
• `1 <= sentence.length <= 10^6`
• `sentence` consists of only lower-case letters and spaces.
• The number of words in `sentence` is in the range `[1, 1000]`
• The length of each word in `sentence` is in the range `[1, 1000]`
• Each two consecutive words in `sentence` will be separated by exactly one space.
• `sentence` does not have leading or trailing spaces.

## Rust Solution

``````struct Solution;
use std::collections::HashMap;

#[derive(Default)]
struct Trie {
children: HashMap<char, Trie>,
end: bool,
}

impl Trie {
fn new() -> Self {
Trie::default()
}

fn insert(&mut self, s: String) {
for c in s.chars() {
}
}

fn map<'a>(&self, s: &'a str) -> &'a str {
for (size, c) in s.char_indices() {
return &s[0..size];
}
if let Some(next) = link.children.get(&c) {
} else {
break;
}
}
s
}
}

impl Solution {
fn replace_words(dict: Vec<String>, sentence: String) -> String {
let mut trie = Trie::new();
for word in dict {
trie.insert(word);
}
sentence
.split_whitespace()
.map(|s| trie.map(s))
.collect::<Vec<&str>>()
.join(" ")
}
}

#[test]
fn test() {
let dict = vec_string!["cat", "bat", "rat"];
let sentence = "the cattle was rattled by the battery".to_string();
let res = "the cat was rat by the bat".to_string();
assert_eq!(Solution::replace_words(dict, sentence), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.