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.

648. Replace Words
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);
}