Longest Word in Dictionary Using Trie in DSA Rust - Build from Scratch

Longest Word in Dictionary Using Trie

📖 Scenario: Imagine you have a list of words from a dictionary. You want to find the longest word that can be built one character at a time by other words in the list. For example, if the word is "apple", then "a", "ap", "app", "appl" must also be in the list. This is useful in games like word building or autocomplete systems.

🎯 Goal: You will build a Trie data structure to store the words. Then, you will find the longest word that can be built step-by-step from other words in the dictionary.

📋 What You'll Learn

Create a TrieNode struct with children and end-of-word marker

Create a Trie struct with insert and search methods

Insert all words into the Trie

Find the longest word that can be built one character at a time using the Trie

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete, spell checkers, and word games to quickly find words and prefixes.

💼 Career

Understanding Tries helps in software roles involving search optimization, text processing, and building efficient data retrieval systems.

1

Create the TrieNode struct

Create a struct called TrieNode with a field children as a vector of Option of size 26, and a boolean field is_end to mark the end of a word. Initialize children with 26 None values and is_end as false.

DSA Rust

# Define the TrieNode struct with children and is_end fields
# Your code here

Hint

Think of children as 26 slots for each letter a-z. Use Option> to allow empty or filled slots.

2

Create the Trie struct and insert method

Create a struct called Trie with a field root of type TrieNode. Implement a method insert(&mut self, word: &str) that inserts a word into the trie by creating nodes for each character and marking the last node's is_end as true.

DSA Rust

struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: TrieNode::new(),
        }
    }

    // Implement insert method here
    // Your code here
}

Hint

Traverse the trie for each character. If child node is missing, create it. Mark the last node as end of word.

3

Insert all words into the Trie

Create a vector called words with these exact strings: "w", "wo", "wor", "worl", "world". Create a mutable Trie instance called trie. Insert each word from words into trie using the insert method.

DSA Rust

let words = vec!["w", "wo", "wor", "worl", "world"];
let mut trie = Trie::new();
// Insert each word into trie
# Your code here

Hint

Use a for loop to insert each word from the words vector into the trie.

4

Find and print the longest word built one character at a time

Implement a function longest_word(trie: &Trie, words: &Vec<String>) -> String that returns the longest word where every prefix is also a word in the trie. Use the is_end property to check prefixes. In main, call longest_word with trie and words and print the result.

DSA Rust

fn longest_word(trie: &Trie, words: &Vec) -> String {
    // Your code here
}

fn main() {
    let words = vec!["w", "wo", "wor", "worl", "world"];
    let mut trie = Trie::new();
    for word in &words {
        trie.insert(word);
    }
    // Call longest_word and print the result
    # Your code here
}

Hint

Check each word if all prefixes are marked as is_end in the trie. Keep track of the longest such word.

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