struct TrieNode {
children: std::collections::HashMap<char, TrieNode>,
is_end: bool,
}
impl TrieNode {
fn new() -> Self {
TrieNode {
children: std::collections::HashMap::new(),
is_end: false,
}
}
}
struct Trie {
root: TrieNode,
}
impl Trie {
fn new() -> Self {
Trie {
root: TrieNode::new(),
}
}
fn insert(&mut self, word: &str) {
let mut node = &mut self.root;
for ch in word.chars() {
node = node.children.entry(ch).or_insert(TrieNode::new());
}
node.is_end = true;
}
fn print(&self) {
fn dfs(node: &TrieNode, prefix: String) {
if node.is_end {
println!("{}", prefix);
}
let mut keys: Vec<_> = node.children.keys().collect();
keys.sort();
for ch in keys {
dfs(&node.children[ch], format!("{}{}", prefix, ch));
}
}
dfs(&self.root, String::new());
}
}
fn main() {
let mut trie = Trie::new();
trie.insert("cat");
trie.insert("car");
trie.insert("cart");
trie.print();
}The Trie stores words by characters. The print function recursively prints words when is_end is true. The children are iterated in the order of the keys in the HashMap, which in Rust is not ordered, but for this challenge, assume alphabetical order for clarity.
Words inserted: "cat", "car", "cart". The printed order is "cat", "car", "cart" because 'a' < 'r' in the second character, but since 'car' and 'cart' share prefix, 'car' prints before 'cart'.
Words: "dog", "dot", "dove"
Shared prefix: "do" (2 nodes)
Then 'g', 't', 'v', 'e' are separate nodes.
Counting nodes:
- 'd' (root child)
- 'o'
- 'g'
- 't'
- 'v'
- 'e'
Total nodes = 7 including the root node.
fn autocomplete(trie: &Trie, prefix: &str) -> Vec<String> { let mut node = &trie.root; for ch in prefix.chars() { if !node.children.contains_key(&ch) { return vec![]; } node = node.children.get(&ch).unwrap(); } let mut results = vec![]; fn dfs(node: &TrieNode, prefix: String, results: &mut Vec<String>) { if node.is_end { results.push(prefix.clone()); } for (ch, child) in &node.children { dfs(child, prefix.clone() + &ch.to_string(), results); } } dfs(node, prefix.to_string(), &mut results); results } // Assume Trie and TrieNode are defined as usual.
The dfs function uses prefix.clone() + &ch.to_string() to build new strings, but the recursive calls use the original prefix variable name, shadowing the outer prefix. This causes the prefix not to accumulate characters properly, so no words are added.
fn insert(&mut self, word: &str) { let mut node = &mut self.root; for ch in word.chars() { node = node.children.entry(ch).or_insert(TrieNode::new()); } node.is_end = true; }
Option A uses or_insert with a function call, which works but creates the object eagerly. Option A uses or_insert_with with a function pointer, which is the idiomatic lazy way.
Options B and D have syntax errors: B uses dot instead of :: and D uses parentheses like a function call on a struct.
fn autocomplete(trie: &Trie, prefix: &str) -> Vec<String> { let mut node = &trie.root; for ch in prefix.chars() { if !node.children.contains_key(&ch) { return vec![]; } node = node.children.get(&ch).unwrap(); } let mut results = vec![]; fn dfs(node: &TrieNode, prefix: String, results: &mut Vec<String>) { if node.is_end { results.push(prefix.clone()); } for (ch, child) in &node.children { dfs(child, prefix.clone() + &ch.to_string(), results); } } dfs(node, prefix.to_string(), &mut results); results } // Assume Trie and TrieNode are defined and words inserted as above.
Words starting with "app" are "app", "apple", and "application". "apt" starts with "ap" but not "app". "banana" does not match.