Prefix Search Using Trie in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths from root to nodes represent prefixes of stored words.

beginner

How does a Trie help in prefix search?

A Trie allows quick prefix search by following the path of characters in the prefix from the root. If the path exists, all words under that node share the prefix.

intermediate

In Rust, what is a common way to represent children nodes in a Trie?

Children nodes are often stored in a HashMap or an array indexed by character to quickly access the next node for a given character.

intermediate

What is the time complexity of prefix search in a Trie?

The time complexity is O(m), where m is the length of the prefix, because we traverse one node per character in the prefix.

beginner

Why is Trie more efficient than a list for prefix search?

Trie avoids checking every word by using shared prefixes, so it only traverses nodes for the prefix length, making prefix search faster than scanning all words.

What does each node in a Trie represent?

A A character of a string

B A whole word

C An integer value

D A prefix length

Each node in a Trie represents a single character of a string.

What data structure is commonly used to store children nodes in a Rust Trie?

A Vector<i32>

B HashMap<char, TrieNode>

C LinkedList<char>

D Binary Tree

HashMap allows quick access to child nodes by character.

What is the main advantage of using a Trie for prefix search?

A Stores numbers efficiently

B Uses less memory than arrays

C Faster search by traversing prefix nodes only

D Sorts words automatically

Trie speeds up prefix search by following the prefix path without scanning all words.

What is the time complexity to search a prefix of length m in a Trie?

A O(m * n)

B O(n)

C O(log n)

D O(m)

Searching a prefix takes O(m) time, where m is the prefix length.

If a prefix does not exist in the Trie, what happens during search?

A Search stops early, returning no matches

B Search continues scanning all words

C Returns the closest word found

D Throws an error

If the prefix path is missing, search stops early with no matches.

Explain how a Trie is structured and how it supports prefix search.

Think about how words share common beginnings.

Describe the steps to insert a word into a Trie and then search for a prefix.

Insertion and search both follow characters step-by-step.

Practice

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

easy

A. To efficiently find all words that start with a given prefix

B. To sort words alphabetically

C. To store numbers in sorted order

D. To perform arithmetic operations quickly

Solution

1. Step 1: Understand Trie usage

   A Trie stores strings in a tree-like structure where each node represents a character, making prefix searches efficient.

2. Step 2: Identify prefix search goal

   Prefix search requires finding all words starting with a given prefix, which Trie supports directly by traversing nodes.

3. Final Answer:

   To efficiently find all words that start with a given prefix -> Option A

4. Quick Check:

   Trie = prefix search efficiency [OK]

Hint: Trie nodes represent characters for fast prefix lookup [OK]

Common Mistakes:

• Confusing Trie with sorting data structure
• Thinking Trie is for numeric operations
• Assuming Trie stores full words only at root

2. Which of the following Rust code snippets correctly defines a Trie node struct for prefix search?

easy

A. struct TrieNode { children: HashMap, is_end: bool }

B. struct TrieNode { children: Vec<char>, is_end: bool }

C. struct TrieNode { children: String, is_end: bool }

D. struct TrieNode { children: i32, is_end: bool }

Solution

1. Step 1: Check children type for TrieNode

   Children must map characters to child nodes, so HashMap is correct for recursive structure without size issues.

2. Step 2: Validate other options

   Vec<char> or String cannot map characters to nodes; i32 is invalid for children.

3. Final Answer:

   struct TrieNode { children: HashMap, is_end: bool } -> Option A

4. Quick Check:

   Children map chars to nodes = struct TrieNode { children: HashMap, is_end: bool } [OK]

Hint: Use HashMap for children in Rust Trie [OK]

Common Mistakes:

• Using Vec<char> instead of mapping to nodes
• Using String for children instead of node references
• Using primitive types like i32 for children

3. Given the following Rust code snippet for inserting words into a Trie and searching for prefix "ca":

let mut trie = Trie::new();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
let result = trie.starts_with("ca");
println!("{:?}", result);

What will be printed?

medium

A. ["cat", "car", "dog"]

B. ["cat", "car"]

C. ["dog"]

D. []

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted. "cat" and "car" share prefix "ca".

2. Step 2: Search for prefix "ca"

   Searching prefix "ca" returns all words starting with "ca", which are "cat" and "car".

3. Final Answer:

   ["cat", "car"] -> Option B

4. Quick Check:

   Prefix "ca" matches cat, car [OK]

Hint: Prefix search returns words starting exactly with given prefix [OK]

Common Mistakes:

• Including words without the prefix
• Returning empty list if prefix exists
• Confusing prefix search with full word search

4. Consider this Rust code snippet for prefix search in a Trie:

fn starts_with(&self, prefix: &str) -> bool {
    let mut node = &self.root;
    for ch in prefix.chars() {
        if !node.children.contains_key(&ch) {
            return false;
        }
        node = node.children.get(&ch).unwrap();
    }
    true
}

What is the main issue with this code snippet?

medium

A. Cannot assign &TrieNode to node because of lifetime mismatch

B. Missing mutable keyword for node variable

C. Using unwrap() without checking Option

D. Incorrect return type for starts_with function

Solution

1. Step 1: Analyze function purpose

   This implements prefix existence check (returns bool).

2. Step 2: Identify mismatch for prefix search

   Prefix search requires returning all words with the prefix (e.g. Vec<String>), not just bool.

3. Final Answer:

   Incorrect return type for starts_with function -> Option D

4. Quick Check:

   Prefix search needs Vec<String> not bool [OK]

Hint: Verify return type matches prefix search requirements [OK]

Common Mistakes:

• Confusing prefix existence (bool) with full prefix search (list)
• Assuming unwrap() causes runtime error here
• Forgetting Rust borrow checker rules

5. You want to extend a Trie in Rust to support prefix search that returns all words starting with a prefix, but also limit results to a maximum of 2 words. Which approach is best?

hard

A. Use a HashSet to store all words and filter after search

B. Store only 2 words per node during insertion

C. Modify DFS traversal to stop collecting words after 2 matches

D. Return only the first word found with the prefix

Solution

1. Step 1: Understand prefix search with limit

   We want to find all words starting with prefix but stop after 2 matches to save time.

2. Step 2: Modify DFS traversal

   During DFS from prefix node, keep count of collected words and stop recursion once 2 words are found.

3. Step 3: Evaluate other options

   Storing only 2 words per node loses data; filtering after search is inefficient; returning one word is incomplete.

4. Final Answer:

   Modify DFS traversal to stop collecting words after 2 matches -> Option C

5. Quick Check:

   Limit results by stopping DFS early [OK]

Hint: Stop DFS early to limit prefix search results [OK]

Common Mistakes:

• Limiting stored words per node loses data
• Filtering after full search wastes time
• Returning only one word ignores requirement