Longest Word in Dictionary Using Trie in DSA Rust

Mental Model

We build a tree where each path from root to a node forms a word prefix. We find the longest word where every prefix is also a word.

Analogy: Imagine a family tree where each generation adds a letter. We want the longest name where every smaller name before it is also in the family.

root
 ↓
 a -> p -> p -> l -> e
       ↓
       e

Each arrow shows a letter link forming words like "apple" and "app".

Dry Run Walkthrough

Input: words: ["a", "app", "apple", "ap", "apply"]

Goal: Find the longest word where all prefixes are also words in the list

Step 1: Insert "a" into trie

root -> a[is_word=true]

Why: Start building trie with first word; mark end of word

Step 2: Insert "ap" into trie

root -> a[is_word=true] -> p[is_word=true]

Why: Add next word; mark end of word at 'p'

Step 3: Insert "app" into trie

root -> a[true] -> p[true] -> p[true]

Why: Add 'app'; mark end of word at second 'p'

Step 4: Insert "apple" into trie

root -> a[true] -> p[true] -> p[true] -> l[false] -> e[true]

Why: Add 'apple'; mark end of word at 'e' node

Step 5: Insert "apply" into trie

root -> a[true] -> p[true] -> p[true] -> l[false] -> y[true]

Why: Add 'apply'; mark end of word at 'y'

Step 6: Search longest word where all prefixes are words

Check 'a', 'ap', 'app', 'appl', 'apple' and 'apply' prefixes

Why: Only words with all prefixes marked as words qualify

Step 7: Find 'apple' and 'apply' both qualify; choose lexicographically smallest

Longest word = 'apple'

Why: Both have all prefixes; 'apple' comes before 'apply'

Result:

root -> a[true] -> p[true] -> p[true] -> l[false] -> e[true]
Longest word: apple

Annotated Code

DSA Rust

use std::collections::HashMap;
use itertools::Itertools;

struct TrieNode {
    children: HashMap<char, TrieNode>,
    is_word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            is_word: 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_with(TrieNode::new);
        }
        node.is_word = true;
    }

    fn longest_word(&self) -> String {
        let mut result = String::new();
        let mut current = String::new();
        self.dfs(&self.root, &mut current, &mut result);
        result
    }

    fn dfs(&self, node: &TrieNode, current: &mut String, result: &mut String) {
        if node != &self.root && !node.is_word {
            return; // stop if prefix is not a word
        }

        if current.len() > result.len() || (current.len() == result.len() && current < result) {
            *result = current.clone();
        }

        for (&ch, child) in node.children.iter().sorted_by_key(|(&c, _)| c) {
            current.push(ch);
            self.dfs(child, current, result);
            current.pop();
        }
    }
}

fn main() {
    let words = vec!["a", "app", "apple", "ap", "apply"];
    let mut trie = Trie::new();
    for word in &words {
        trie.insert(word);
    }
    let longest = trie.longest_word();
    println!("Longest word: {}", longest);
}

node = node.children.entry(ch).or_insert_with(TrieNode::new);

advance or create child node for each character

node.is_word = true;

mark end of inserted word

if node != &self.root && !node.is_word { return; }

stop DFS if current prefix is not a word

if current.len() > result.len() || (current.len() == result.len() && current < result) { *result = current.clone(); }

update longest word if current is longer or lex smaller

for (&ch, child) in node.children.iter().sorted_by_key(|(&c, _)| c) { current.push(ch); self.dfs(child, current, result); current.pop(); }

explore children in alphabetical order to find lex smallest

Output

Longest word: apple

Complexity Analysis

Time: O(N * L) where N is number of words and L is average length, because we insert all words and DFS all nodes once

Space: O(N * L) for trie storage of all characters in all words

vs Alternative: Compared to sorting and checking prefixes in array (O(N log N * L)), trie offers efficient prefix checks and lex order traversal

Edge Cases

Empty word list

Returns empty string as no words exist

DSA Rust

if node != &self.root && !node.is_word { return; }

Words with single character only

Returns the longest single character word (lex smallest if multiple)

DSA Rust

if current.len() > result.len() || (current.len() == result.len() && current < result) { *result = current.clone(); }

Words where some prefixes are missing

Ignores words whose prefixes are not all words

DSA Rust

if node != &self.root && !node.is_word { return; }

When to Use This Pattern

When asked to find the longest word with all prefixes present, use a trie to efficiently check prefixes and traverse lex order.

Common Mistakes

Mistake: Not checking if all prefixes are words before continuing DFS
Fix: Add condition to stop DFS if current prefix node is not marked as a word

Mistake: Not sorting children during DFS causing wrong lex order
Fix: Sort children keys before DFS to ensure lexicographically smallest word is chosen

Summary

Build a trie from words and find the longest word where every prefix is also a word.

Use when you need to find words with valid prefixes efficiently and lex order matters.

The key is to stop exploring paths where prefixes are missing and to traverse children in alphabetical order.

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To reverse the words quickly

B. To sort words alphabetically

C. To count the total number of words

D. To efficiently store and search words by their prefixes

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by their prefixes, allowing quick prefix checks.

2. Step 2: Relate to longest word search

   Finding the longest word with all prefixes present is easier with Trie traversal.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option D

4. Quick Check:

   Trie = prefix-based search [OK]

Hint: Trie is all about prefixes and fast prefix lookups [OK]

Common Mistakes:

• Confusing Trie with sorting structure
• Thinking Trie counts words only
• Assuming Trie reverses words

2. Which of the following Rust code snippets correctly defines a Trie node struct for storing children nodes?

easy

A. struct TrieNode { children: [Option; 26] }

B. struct TrieNode { children: HashMap }

C. struct TrieNode { children: Vec> }

D. struct TrieNode { children: Vec<TrieNode> }

Solution

1. Step 1: Understand Trie children representation

   Each node has fixed 26 children for letters a-z, stored as array of Options.

2. Step 2: Check Rust syntax correctness

   Option allows nullable child nodes; array size 26 matches alphabet.

3. Final Answer:

   struct TrieNode { children: [Option; 26] } -> Option A

4. Quick Check:

   Fixed-size array with Option<Box> = correct Trie node [OK]

Hint: Use fixed-size array with Option<Box> for children in Rust Trie [OK]

Common Mistakes:

• Using Vec without fixed size wastes memory
• Using HashMap without Box causes ownership errors
• Not wrapping children in Option causes panic

3. Given the following Rust code snippet that inserts words into a Trie and finds the longest word with all prefixes present, what will be the printed output?

let words = vec!["a", "app", "ap", "apply", "apple"];
let longest = find_longest_word(words);
println!("{}", longest);

Assume find_longest_word uses a Trie to find the longest word where every prefix is also a word.

medium

A. "apple"

B. "apply"

C. "app"

D. "ap"

Solution

1. Step 1: Check prefixes for each word

   "apple" prefixes: a, ap, app, appl; "appl" missing, so invalid.
   "apply" prefixes: a, ap, app, appl; "appl" missing, invalid.
   "app" prefixes: a, ap, app; all present.
   "ap" prefixes: a, ap; all present.

2. Step 2: Find longest valid word

   "app" is longest word with all prefixes present.

3. Final Answer:

   "app" -> Option C

4. Quick Check:

   Longest word with all prefixes = "app" [OK]

Hint: Check all prefixes exist before choosing longest word [OK]

Common Mistakes:

• Assuming 'apple' or 'apply' are valid without all prefixes
• Ignoring prefix 'appl' missing
• Choosing shortest word instead of longest

4. The following Rust function attempts to insert words into a Trie and find the longest word with all prefixes present. It compiles but returns an empty string. What is the likely bug?

fn find_longest_word(words: Vec<&str>) -> String {
    let mut trie = Trie::new();
    for word in &words {
        trie.insert(word);
    }
    trie.search_longest_word()
}

// Trie methods:
// insert(&self, word: &str)
// search_longest_word(&self) -> String

medium

A. The function should return &str, not String

B. The insert method should take &mut self, not &self

C. Words vector should be mutable

D. The search_longest_word method should take &mut self, not &self

Solution

1. Step 1: Analyze method signatures

   Inserting words modifies Trie, so insert must take mutable reference &mut self.

2. Step 2: Identify compilation vs runtime issue

   Code compiles but insert called with &self means no actual insertion happens, so Trie remains empty.

3. Final Answer:

   The insert method should take &mut self, not &self -> Option B

4. Quick Check:

   Mutable insert needed for Trie modification [OK]

Hint: Insert modifies Trie; needs &mut self in Rust [OK]

Common Mistakes:

• Thinking search needs mutable reference
• Making words vector mutable unnecessarily
• Returning wrong type String vs &str

5. You have a list of words: ["a", "banana", "app", "appl", "ap", "apply", "apple"]. Using a Trie, which word will be returned as the longest word where every prefix is also a word? Explain why the word "banana" is not chosen.

hard

A. "apple" because "banana" prefixes are missing

B. "apply" because it is longer than "apple"

C. "appl" because "appl" is a prefix of "apple" and "apply"

D. "apple" because all its prefixes exist

Solution

1. Step 1: Check prefixes of each candidate word

   "apple" prefixes: a, ap, app, appl, apple - all present.
   "apply" prefixes: a, ap, app, appl, apply - all present.
   "banana" prefixes: b, ba, ban, bana, banan, banana - none except 'b' likely missing.

2. Step 2: Understand why "banana" is excluded

   Since prefixes like 'b', 'ba' are not in the word list, "banana" is invalid.
   Between "apple" and "apply", both valid, but "apple" is chosen (depends on lex order or implementation).

3. Final Answer:

   "apple" because "banana" prefixes are missing -> Option A

4. Quick Check:

   Missing prefixes exclude "banana" [OK]

Hint: Check all prefixes exist; missing prefixes exclude word [OK]

Common Mistakes:

• Assuming "banana" is valid without prefixes
• Confusing "apply" as longer than "apple"
• Ignoring prefix checks for all words