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.
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:
words
will be in the range [1, 1000]
.words[i]
will be in the range [1, 30]
.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);
}
Having problems with this solution? Click here to submit an issue on github.