720. Longest Word in Dictionary

Given a list of strings `words` representing an English Dictionary, find the longest word in `words` that can be built one character at a time by other words in `words`. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

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

Example 2:

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

Note:

• All the strings in the input will only contain lowercase letters.
• The length of `words` will be in the range `[1, 1000]`.
• The length of `words[i]` will be in the range `[1, 30]`.
• 720. Longest Word in Dictionary
``````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) {
for c in s.chars() {
}
}
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);
}
``````