Trie vs Hash Map for Prefix Matching in DSA C++ - Build Both Approaches

Trie vs Hash Map for Prefix Matching

📖 Scenario: Imagine you are building a simple search feature for a phone contact list. You want to find all contacts that start with a certain prefix quickly.

🎯 Goal: You will create a small program that stores contact names and then finds all names starting with a given prefix using two methods: a Trie and a Hash Map. This will help you understand how these data structures work for prefix matching.

📋 What You'll Learn

Create a list of contact names

Create a prefix string to search

Implement prefix matching using a Trie

Implement prefix matching using a Hash Map

Print the matching contacts from both methods

💡 Why This Matters

🌍 Real World

Search features in phone contacts, autocomplete in search engines, and dictionary word lookups use prefix matching to quickly find relevant results.

💼 Career

Understanding Tries and Hash Maps for prefix matching is useful for software engineers working on search engines, text editors, and any application requiring fast lookup of strings.

1

Create the list of contacts

Create a std::vector<std::string> called contacts with these exact names: "Alice", "Bob", "Alfred", "Bobby", and "Alex".

DSA C++

# Create the contacts vector with the given names
# Your code here

Hint

Use std::vector<std::string> and initialize it with the exact names inside curly braces.

2

Create the prefix to search

Create a std::string variable called prefix and set it to "Al".

DSA C++

#include 
#include 
#include 

std::vector contacts = {"Alice", "Bob", "Alfred", "Bobby", "Alex"};

# Create the prefix string
# Your code here

Hint

Use std::string prefix = "Al"; to create the prefix variable.

3

Implement prefix matching using a Trie

Implement a simple Trie class with insert and startsWith methods. Insert all contacts into the Trie. Then create a function getContactsWithPrefixTrie that returns a std::vector<std::string> of all contacts starting with prefix using the Trie.

DSA C++

#include 
#include 
#include 

std::vector contacts = {"Alice", "Bob", "Alfred", "Bobby", "Alex"};

std::string prefix = "Al";

// Implement Trie class and getContactsWithPrefixTrie function
// Your code here

Hint

Build a Trie with insert and startsWithNode methods. Use a depth-first search to collect all words starting with the prefix.

4

Print matching contacts from Trie and Hash Map

Print the contacts starting with prefix found by getContactsWithPrefixTrie. Then create a std::unordered_map<std::string, bool> called contactMap with all contacts as keys. Use a loop to find and print all contacts starting with prefix from contactMap.

DSA C++

#include 
#include 
#include 
#include 

std::vector contacts = {"Alice", "Bob", "Alfred", "Bobby", "Alex"};

std::string prefix = "Al";

// Trie and helper functions already defined above

int main() {
    // Print contacts from Trie
    // Your code here

    // Create contactMap and print contacts starting with prefix
    // Your code here

    return 0;
}

Hint

Use getContactsWithPrefixTrie to get and print contacts from the Trie. Then create a std::unordered_map<std::string, bool> with all contacts and print those starting with prefix by checking if pair.first.find(prefix) == 0.