720. Longest Word in Dictionary

Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Input: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: 
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Rust Solution

struct Solution;

use std::collections::BTreeMap;

#[derive(Debug, PartialEq, Eq, Clone, Default)]
struct Trie {
    children: BTreeMap<char, Trie>,
    end: bool,
}

impl Trie {
    fn new() -> Self {
        Self::default()
    }
    fn from_words(words: Vec<String>) -> Self {
        let mut trie = Trie::new();
        for word in words {
            trie.insert(word);
        }
        trie
    }
    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 dfs(&self, s: &mut String, max: &mut String) {
        if self.end {
            if s.len() > max.len() {
                *max = s.clone();
            }
        }
        if s.is_empty() || self.end {
            for (&c, child) in self.children.iter() {
                s.push(c);
                child.dfs(s, max);
                s.pop();
            }
        }
    }
}

impl Solution {
    fn longest_word(words: Vec<String>) -> String {
        let trie = Trie::from_words(words);
        let mut s: String = "".to_string();
        let mut max: String = "".to_string();
        trie.dfs(&mut s, &mut max);
        max
    }
}

#[test]
fn test() {
    let words: Vec<String> = vec_string!["a", "banana", "app", "appl", "ap", "apply", "apple"];
    let res = "apple".to_string();
    assert_eq!(Solution::longest_word(words), res);
}