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

Trie vs Hash Map for Prefix Matching

📖 Scenario: You are building a simple search feature for a phone contacts app. Users want to find contacts quickly by typing the first few letters of a name.Two common ways to do this are using a Trie data structure or a Hash Map that stores names by their prefixes.

🎯 Goal: Build a program that stores a list of contact names and then finds all contacts starting with a given prefix using both a Trie and a Hash Map. Compare how each method works.

📋 What You'll Learn

Create a list of contact names

Create a dictionary (hash map) that maps prefixes to lists of names

Build a Trie data structure to store the names

Write functions to find all names starting with a prefix using both methods

Print the results of prefix searches

💡 Why This Matters

🌍 Real World

Prefix matching is used in search bars, autocomplete features, and contact lists to quickly find items starting with typed letters.

💼 Career

Understanding Tries and hash maps for prefix matching is useful for software engineers working on search engines, mobile apps, and any system requiring fast text lookup.

1

Create the list of contact names

Create a list called contacts with these exact names: "Alice", "Bob", "Alfred", "Bobby", "Alex"

DSA C#

# Create the list of contact names
# Your code here

Hint

Use List<string> and initialize it with the exact names inside curly braces.

2

Create a hash map of prefixes to names

Create a dictionary called prefixMap of type Dictionary<string, List<string>>. For each contact in contacts, add all prefixes (from first letter up to full name) as keys. Each key should map to a list of names starting with that prefix.

DSA C#

using System.Collections.Generic;

List contacts = new List { "Alice", "Bob", "Alfred", "Bobby", "Alex" };

// Create the prefixMap dictionary and fill it
# Your code here

Hint

Use nested loops: outer loop over contacts, inner loop to get prefixes using Substring. Add names to lists in prefixMap.

3

Build a Trie to store the contacts

Define a class TrieNode with a dictionary children of type Dictionary<char, TrieNode> and a boolean isEndOfWord. Then create a class Trie with a root node. Add a method Insert(string word) to add each contact to the Trie.

DSA C#

using System.Collections.Generic;

List contacts = new List { "Alice", "Bob", "Alfred", "Bobby", "Alex" };

Dictionary> prefixMap = new Dictionary>();

foreach (string name in contacts)
{
    for (int i = 1; i ();
        }
        prefixMap[prefix].Add(name);
    }
}

// Define TrieNode and Trie classes with Insert method
# Your code here

Hint

Define TrieNode with children dictionary and end flag. Define Trie with root node and Insert method that walks through characters.

4

Search and print names starting with a prefix

Write code to find and print all names starting with prefix "Al" using prefixMap. Then write a method SearchPrefix(string prefix) in Trie that returns all names starting with the prefix. Print those results too.

DSA C#

using System.Collections.Generic;
using System;

List contacts = new List { "Alice", "Bob", "Alfred", "Bobby", "Alex" };

Dictionary> prefixMap = new Dictionary>();

foreach (string name in contacts)
{
    for (int i = 1; i ();
        }
        prefixMap[prefix].Add(name);
    }
}

class TrieNode
{
    public Dictionary children = new Dictionary();
    public bool isEndOfWord = false;
}

class Trie
{
    private TrieNode root = new TrieNode();

    public void Insert(string word)
    {
        TrieNode node = root;
        foreach (char c in word)
        {
            if (!node.children.ContainsKey(c))
            {
                node.children[c] = new TrieNode();
            }
            node = node.children[c];
        }
        node.isEndOfWord = true;
    }

    // Add SearchPrefix method here
    # Your code here
}

Trie trie = new Trie();
foreach (string name in contacts)
{
    trie.Insert(name);
}

// Print names from prefixMap for prefix "Al"
// Print names from trie.SearchPrefix("Al")

Hint

Use prefixMap["Al"] to print names. In Trie, add SearchPrefix method that finds the node for prefix and collects all words below it using DFS.

Practice

1. Which data structure is generally more efficient for prefix matching when dealing with a large set of strings?

easy

A. Array, because it stores elements in contiguous memory

B. Hash Map, because it stores keys and values with constant time lookup

C. Trie, because it stores prefixes explicitly and allows fast prefix searches

D. Linked List, because it allows sequential access

Solution

1. Step 1: Understand prefix matching requirements

   Prefix matching requires checking if a string starts with a given prefix efficiently.

2. Step 2: Compare Trie and Hash Map for prefix matching

   Trie stores prefixes explicitly, enabling fast prefix search. Hash Map is good for exact key lookup but not efficient for prefix queries.

3. Final Answer:

   Trie, because it stores prefixes explicitly and allows fast prefix searches -> Option C

4. Quick Check:

   Prefix matching = Trie [OK]

Hint: Trie stores prefixes explicitly, ideal for prefix search [OK]

Common Mistakes:

• Thinking hash map supports prefix search efficiently
• Confusing array or linked list with prefix matching
• Ignoring the need for prefix traversal

2. Which of the following is the correct way to declare a Trie node class in C#?

easy

A. public class TrieNode { public int[] Children = new int[26]; public bool IsEndOfWord; }

B. public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord; }

C. public class TrieNode { public List<int> Children; public bool IsEndOfWord; }

D. public class TrieNode { public string Children; public bool IsEndOfWord; }

Solution

1. Step 1: Identify the correct data type for children in TrieNode

   Children should map characters to TrieNode references, so Dictionary is appropriate.

2. Step 2: Check other options for correctness

   List<int> or int[] do not map characters to nodes directly; string is incorrect for children representation.

3. Final Answer:

   public class TrieNode { public Dictionary Children = new Dictionary(); public bool IsEndOfWord; } -> Option B

4. Quick Check:

   TrieNode children = Dictionary [OK]

Hint: Trie children map chars to nodes using Dictionary [OK]

Common Mistakes:

• Using List<int> or int[] instead of Dictionary
• Using string type for children
• Not initializing the dictionary

3. What will be the output of the following C# code snippet?

var trie = new Trie();
trie.Insert("apple");
trie.Insert("app");
Console.WriteLine(trie.StartsWith("app"));
Console.WriteLine(trie.StartsWith("apl"));

Assuming Trie class has Insert and StartsWith methods implemented correctly.

medium

A. True
False

B. False
True

C. True
True

D. False
False

Solution

1. Step 1: Insert words "apple" and "app" into the Trie

   Both words share prefix "app", so Trie stores nodes for 'a', 'p', 'p', and further for 'l', 'e'.

2. Step 2: Check StartsWith("app") and StartsWith("apl")

   "app" is a prefix present in Trie, so returns True. "apl" is not a prefix of any inserted word, so returns False.

3. Final Answer:

   True False -> Option A

4. Quick Check:

   StartsWith("app")=True, StartsWith("apl")=False [OK]

Hint: Check if prefix exists exactly in Trie nodes [OK]

Common Mistakes:

• Assuming "apl" prefix exists
• Confusing Insert with StartsWith
• Mixing up True/False outputs

4. The following code tries to use a HashMap to check if any word starts with a given prefix. What is the main issue?

var map = new Dictionary();
map["apple"] = true;
map["app"] = true;

bool StartsWith(string prefix) {
    return map.ContainsKey(prefix);
}

Console.WriteLine(StartsWith("app"));
Console.WriteLine(StartsWith("apl"));

medium

A. HashMap does not support prefix search; ContainsKey checks exact keys only

B. The dictionary keys are not initialized properly

C. The StartsWith method should use map.Values instead of map.Keys

D. The code will throw a runtime exception

Solution

1. Step 1: Understand what ContainsKey does in Dictionary

   ContainsKey checks if the exact key exists, not if any key starts with the prefix.

2. Step 2: Identify why prefix search fails

   Since map only stores full words as keys, ContainsKey("app") returns true only if "app" is a full key, not if any key starts with "app".

3. Final Answer:

   HashMap does not support prefix search; ContainsKey checks exact keys only -> Option A

4. Quick Check:

   HashMap prefix search = no [OK]

Hint: ContainsKey checks exact keys, not prefixes [OK]

Common Mistakes:

• Thinking ContainsKey supports prefix matching
• Assuming dictionary keys are incomplete
• Expecting runtime errors

5. You need to implement a system that supports fast prefix queries and also stores frequency counts of words. Which approach is best and why?

hard

A. Hash Map storing only full word frequencies, no prefix support

B. Hash Map with prefix keys, but inefficient for large prefix sets

C. Trie with frequencies only at leaf nodes, no prefix counts

D. Trie with frequency counts at each node for prefix frequency queries

Solution

1. Step 1: Analyze prefix query and frequency requirements

   We want to query frequencies of prefixes, not just full words.

2. Step 2: Evaluate each approach

   A Trie with frequency counts at each node allows quick prefix frequency queries. Hash Map with full words only cannot query prefixes efficiently. Trie with frequencies only at leaves misses prefix counts. Hash Map with prefix keys is inefficient for many prefixes.

3. Final Answer:

   Trie with frequency counts at each node for prefix frequency queries -> Option D

4. Quick Check:

   Prefix frequency queries = Trie with node counts [OK]

Hint: Store counts at each Trie node for prefix frequency queries [OK]

Common Mistakes:

• Using Hash Map only for prefix queries
• Storing frequencies only at leaf nodes
• Assuming prefix keys in Hash Map scale well