Word Search in Trie in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to insert a character into the children map of the Trie node.

DSA Rust

self.children.insert([1], TrieNode::new());

Drag options to blanks, or click blank then click option'

A'c'

B'z'

C'a'

D'x'

Attempts:

3 left

💡 Hint

Common Mistakes

Using uppercase letters instead of lowercase.

Inserting a character not present in the word.

The character 'a' is inserted as a key in the children map to create a new TrieNode.

2fill in blank

medium

Complete the code to check if the current character exists in the children map during search.

DSA Rust

if !node.children.contains_key(&[1]) { return false; }

Drag options to blanks, or click blank then click option'

A'a'

B'b'

C'd'

D'e'

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for a character not in the word.

Using a character without referencing it correctly.

We check if the character 'a' exists in the children map to continue the search.

3fill in blank

hard

Fix the error in the code to move to the next Trie node during search.

DSA Rust

node = node.children.get(&[1]).unwrap();

Drag options to blanks, or click blank then click option'

A'c'

B'd'

C'b'

D'a'

Attempts:

3 left

💡 Hint

Common Mistakes

Using a character not present in the children map.

Not unwrapping the Option returned by get().

We get the child node corresponding to character 'a' to continue traversal.

4fill in blank

hard

Fill both blanks to complete the loop that inserts each character of the word into the Trie.

DSA Rust

for ch in word.[1]() {
    node = node.children.entry(ch).or_insert([2]);
}

Drag options to blanks, or click blank then click option'

Aiter()

BTrieNode::new()

Cchars()

DVec::new()

Attempts:

3 left

💡 Hint

Common Mistakes

Using iter() on a string which returns bytes, not chars.

Inserting a Vec instead of a TrieNode.

We iterate over each character using chars() and insert new TrieNode if missing.

5fill in blank

hard

Fill all three blanks to complete the search function that returns true if the word exists in the Trie.

DSA Rust

let mut node = &self.root;
for ch in word.[1]() {
    if !node.children.[2](&ch) {
        return false;
    }
    node = node.children.[3](&ch).unwrap();
}
node.is_end_of_word

Drag options to blanks, or click blank then click option'

Achars

Bcontains_key

Cget

Diter

Attempts:

3 left

💡 Hint

Common Mistakes

Using iter() which returns bytes, not characters.

Using get() without checking contains_key() first.

Not unwrapping the Option returned by get().

We iterate over characters, check if child exists with contains_key, then get the child node.

Practice

1. What is the main purpose of using a Trie data structure in word search problems?

easy

A. To sort words alphabetically

B. To store words in a hash table

C. To efficiently store and search words by their prefixes

D. To perform arithmetic operations on words

Solution

1. Step 1: Understand Trie structure

   A Trie stores characters in nodes where each path from root to a node represents a prefix of words.

2. Step 2: Purpose in word search

   This structure allows quick prefix checks and word searches, making it efficient for word search problems.

3. Final Answer:

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

4. Quick Check:

   Trie = Prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Confusing Trie with hash tables
• Thinking Trie sorts words
• Assuming Trie stores whole words only

2. Which of the following is the correct Rust syntax to define a Trie node struct with a children field as a vector of optional boxed Trie nodes?

easy

A. struct TrieNode { children: Vec> }

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

C. struct TrieNode { children: Option> }

D. struct TrieNode { children: Box> }

Solution

1. Step 1: Understand Rust ownership and pointers

   To allow recursive data structures, Rust uses Box to allocate on heap and Option for nullable children.

2. Step 2: Correct syntax for children field

   Children should be a vector of optional boxed TrieNode references: Vec>.

3. Final Answer:

   struct TrieNode { children: Vec> } -> Option A

4. Quick Check:

   Recursive struct uses Box and Option [OK]

Hint: Use Box and Option for recursive Trie nodes in Rust [OK]

Common Mistakes:

• Using Vec<TrieNode> causes infinite size error
• Wrapping Vec in Option instead of elements
• Incorrect Box placement

3. Given the following Rust code snippet for searching a word in a Trie, what will be the output printed?

struct TrieNode {
    children: Vec>,
    is_end: bool,
}

impl TrieNode {
    fn search(&self, word: &str) -> bool {
        let mut node = self;
        for ch in word.chars() {
            let index = (ch as usize) - ('a' as usize);
            match &node.children[index] {
                Some(child) => node = child,
                None => return false,
            }
        }
        node.is_end
    }
}

fn main() {
    let mut root = TrieNode {
        children: vec![None; 26],
        is_end: false,
    };
    println!("{}", root.search("cat"));
    println!("{}", root.search("car"));
}

medium

A. true
false

B. false
false

C. true
true

D. Compilation error

Solution

1. Step 1: Analyze search function behavior

   The search returns true if all characters are found and the last node marks end of a word.

2. Step 2: Check given calls

   No words are inserted; root.children initialized to vec![None; 26]. For "cat" and "car", first char 'c' (index 2) is None, so both return false.

3. Final Answer:

   false false -> Option B

4. Quick Check:

   Search returns false for non-inserted words [OK]

Hint: Search returns true only if full word exists [OK]

Common Mistakes:

• Assuming partial prefix returns true
• Ignoring is_end flag
• Confusing character indexing

4. Identify the bug in this Rust Trie search method and select the correct fix:

fn search(&self, word: &str) -> bool {
    let mut node = self;
    for ch in word.chars() {
        let index = (ch as usize) - ('a' as usize);
        if node.children[index].is_some() {
            node = &node.children[index].unwrap();
        } else {
            return false;
        }
    }
    true
}

medium

A. Return node.is_end instead of true at the end

B. Change unwrap() to expect() with error message

C. Use mutable reference for node variable

D. Initialize children vector with 26 None elements

Solution

1. Step 1: Understand search logic

   The method should return true only if the word ends at a node marked as end of a word.

2. Step 2: Identify bug in return statement

   Returning true always ignores if the node marks end of a word; must return node.is_end.

3. Final Answer:

   Return node.is_end instead of true at the end -> Option A

4. Quick Check:

   Search must check is_end flag [OK]

Hint: Always check is_end flag after traversal [OK]

Common Mistakes:

• Returning true without checking is_end
• Ignoring None cases
• Misusing unwrap without safety

5. You want to implement a function in Rust that searches for all words in a Trie starting with a given prefix. Which approach correctly combines Trie traversal and word collection?

hard

A. Use a hash map to map prefixes to words and lookup directly

B. Search each word in Trie individually to check prefix match

C. Store all words in a vector and filter by prefix using string starts_with

D. Traverse Trie nodes for prefix, then recursively collect all words from that node

Solution

1. Step 1: Traverse Trie for prefix

   Follow nodes for each character in prefix to reach prefix node.

2. Step 2: Collect words recursively

   From prefix node, recursively explore children to collect all complete words.

3. Final Answer:

   Traverse Trie nodes for prefix, then recursively collect all words from that node -> Option D

4. Quick Check:

   Prefix traversal + recursive collection = A [OK]

Hint: Find prefix node, then gather words recursively [OK]

Common Mistakes:

• Checking all words instead of prefix traversal
• Using external data structures unnecessarily
• Ignoring recursive collection after prefix