Word Search in Trie in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie Word Search Result

What is the output of the following Rust code that inserts words into a Trie and searches for a specific word?

DSA Rust

struct TrieNode {
    children: [Option<Box<TrieNode>>; 26],
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        Self {
            children: Default::default(),
            is_end: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

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

    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            let idx = (ch as u8 - b'a') as usize;
            if node.children[idx].is_none() {
                node.children[idx] = Some(Box::new(TrieNode::new()));
            }
            node = node.children[idx].as_mut().unwrap();
        }
        node.is_end = true;
    }

    fn search(&self, word: &str) -> bool {
        let mut node = &self.root;
        for ch in word.chars() {
            let idx = (ch as u8 - b'a') as usize;
            if node.children[idx].is_none() {
                return false;
            }
            node = node.children[idx].as_ref().unwrap();
        }
        node.is_end
    }
}

fn main() {
    let mut trie = Trie::new();
    trie.insert("apple");
    trie.insert("app");
    trie.insert("bat");
    println!("{}", trie.search("app"));
    println!("{}", trie.search("apple"));
    println!("{}", trie.search("bat"));
    println!("{}", trie.search("bath"));
}

A

true
false
true
false

B

true
true
true
false

C

false
true
true
false

D

true
true
false
false

💡 Hint

Trace the insertions and check if the search word ends at a node marked as end of a word.

The words 'app', 'apple', and 'bat' are inserted. Searching 'app', 'apple', and 'bat' returns true because they were inserted. Searching 'bath' returns false because it was not inserted.

🧠 Conceptual

intermediate

Trie Node Children Representation

In a Trie implementation for lowercase English letters, what is the best way to represent the children nodes of each TrieNode?

A A vector that dynamically grows as new children are added

B A HashMap mapping characters to TrieNode references

C An array of size 26 where each index corresponds to a letter, storing Option<Box<TrieNode>>

D A linked list of child nodes storing characters and pointers

💡 Hint

Consider fixed alphabet size and fast access by index.

Using a fixed-size array of 26 elements allows O(1) access to children nodes for each letter, which is efficient for fixed alphabets like lowercase English letters.

🔧 Debug

advanced

Identify the Bug in Trie Search Method

What error will occur when running this Rust Trie search method if the word contains uppercase letters?

DSA Rust

fn search(&self, word: &str) -> bool {
    let mut node = &self.root;
    for ch in word.chars() {
        let idx = (ch as u8 - b'a') as usize;
        if node.children[idx].is_none() {
            return false;
        }
        node = node.children[idx].as_ref().unwrap();
    }
    node.is_end
}

A Panic due to index out of bounds when uppercase letter is converted

B Returns false silently for uppercase letters

C Compilation error due to invalid cast

D Infinite loop during search

💡 Hint

Check how uppercase letters convert to indices.

Uppercase letters have ASCII codes less than 'a', so subtracting 'a' results in a large usize causing index out of bounds panic.

🚀 Application

advanced

Find All Words with Given Prefix in Trie

Given a Trie with inserted words, which method correctly collects all words starting with a given prefix?

DSA Rust

fn collect_words(node: &TrieNode, prefix: &mut String, results: &mut Vec<String>) {
    if node.is_end {
        results.push(prefix.clone());
    }
    for i in 0..26 {
        if let Some(child) = &node.children[i] {
            prefix.push((b'a' + i as u8) as char);
            collect_words(child, prefix, results);
            prefix.pop();
        }
    }
}

fn words_with_prefix(trie: &Trie, prefix: &str) -> Vec<String> {
    let mut node = &trie.root;
    for ch in prefix.chars() {
        let idx = (ch as u8 - b'a') as usize;
        if node.children[idx].is_none() {
            return vec![];
        }
        node = node.children[idx].as_ref().unwrap();
    }
    let mut results = Vec::new();
    let mut prefix_string = prefix.to_string();
    collect_words(node, &mut prefix_string, &mut results);
    results
}

A Returns an empty vector always

B Returns only the prefix itself if it is a word

C Returns all words in the Trie regardless of prefix

D Returns all words starting with prefix by DFS from prefix node

💡 Hint

After reaching prefix node, explore all child paths recursively.

The method finds the node matching the prefix, then uses DFS to collect all words starting from that node.

❓ Predict Output

expert

Output of Trie Search with Backtracking Word Search

What is the output of this Rust code that uses a Trie to check if a word can be formed by concatenating two words from the Trie?

DSA Rust

struct TrieNode {
    children: [Option<Box<TrieNode>>; 26],
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        Self {
            children: Default::default(),
            is_end: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

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

    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            let idx = (ch as u8 - b'a') as usize;
            if node.children[idx].is_none() {
                node.children[idx] = Some(Box::new(TrieNode::new()));
            }
            node = node.children[idx].as_mut().unwrap();
        }
        node.is_end = true;
    }

    fn search(&self, word: &str) -> bool {
        let mut node = &self.root;
        for ch in word.chars() {
            let idx = (ch as u8 - b'a') as usize;
            if node.children[idx].is_none() {
                return false;
            }
            node = node.children[idx].as_ref().unwrap();
        }
        node.is_end
    }

    fn can_form_by_two_words(&self, word: &str) -> bool {
        fn backtrack(trie: &Trie, word: &str, start: usize, count: usize) -> bool {
            if start == word.len() {
                return count == 2;
            }
            let mut node = &trie.root;
            for i in start..word.len() {
                let idx = (word.as_bytes()[i] - b'a') as usize;
                if node.children[idx].is_none() {
                    return false;
                }
                node = node.children[idx].as_ref().unwrap();
                if node.is_end {
                    if backtrack(trie, word, i + 1, count + 1) {
                        return true;
                    }
                }
            }
            false
        }
        backtrack(self, word, 0, 0)
    }
}

fn main() {
    let mut trie = Trie::new();
    trie.insert("cat");
    trie.insert("dog");
    trie.insert("cats");
    trie.insert("sand");
    trie.insert("and");
    println!("{}", trie.can_form_by_two_words("catsand"));
    println!("{}", trie.can_form_by_two_words("catdog"));
    println!("{}", trie.can_form_by_two_words("catsanddog"));
}

A

true
true
false

B

false
true
true

C

true
false
false

D

false
false
true

💡 Hint

Check if the word can be split into exactly two words from the Trie.

"catsand" can be split as "cats" + "and" (both in Trie), returns true. "catdog" can be split as "cat" + "dog", returns true. "catsanddog" requires more than two words, returns false.

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