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) {
let mut link = self;
for c in s.chars() {
link = link.children.entry(c).or_default();
}
link.end = true;
}
fn map<'a>(&self, s: &'a str) -> &'a str {
let mut link = self;
for (size, c) in s.char_indices() {
if link.end {
return &s[0..size];
}
if let Some(next) = link.children.get(&c) {
link = next;
} 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.