Trie vs Hash Map for Prefix Matching in DSA Python - 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 whose names start with a certain prefix quickly.

🎯 Goal: Build two ways to find contacts by prefix: one using a dictionary (hash map) and one using a Trie (prefix tree). Compare how they store and search prefixes.

📋 What You'll Learn

Create a list of contact names

Create a prefix string to search

Implement prefix search using a dictionary (hash map)

Implement prefix search using a Trie data structure

Print the results of both searches

💡 Why This Matters

🌍 Real World

Phone contact search, autocomplete in search bars, and word games use prefix matching to quickly find words or names.

💼 Career

Understanding Tries and hash maps helps in roles like software development, data engineering, and search engine optimization where fast lookup is important.

1

Create the contact list

Create a list called contacts with these exact names: 'Alice', 'Bob', 'Alfred', 'Bobby', 'Albert'.

DSA Python

# Create the list of contacts
# Your code here

Hint

Use square brackets and quotes for each name, separated by commas.

2

Set the prefix to search

Create a variable called prefix and set it to the string 'Al'.

DSA Python

contacts = ['Alice', 'Bob', 'Alfred', 'Bobby', 'Albert']
# Set the prefix string to 'Al'
# Your code here

Hint

Use single or double quotes around 'Al'.

3

Implement prefix search using a dictionary (hash map)

Create a dictionary called contact_map where keys are contact names and values are True. Then create a list called hash_map_results that contains all names from contact_map starting with prefix using a for loop and if condition.

DSA Python

contacts = ['Alice', 'Bob', 'Alfred', 'Bobby', 'Albert']
prefix = 'Al'
# Create contact_map dictionary and find names starting with prefix
# Your code here

Hint

Use dictionary comprehension to create contact_map. Use startswith() to check prefix.

4

Implement prefix search using a Trie and print results

Define a class TrieNode with a dictionary children and a boolean is_end. Define a class Trie with methods insert(word) and search_prefix(prefix) that returns all words starting with prefix. Insert all contacts into the Trie. Use search_prefix(prefix) to get trie_results. Finally, print hash_map_results and trie_results.

DSA Python

contacts = ['Alice', 'Bob', 'Alfred', 'Bobby', 'Albert']
prefix = 'Al'
contact_map = {name: True for name in contacts}
hash_map_results = []
for name in contact_map:
    if name.startswith(prefix):
        hash_map_results.append(name)

# Define TrieNode and Trie classes, insert contacts, search prefix, and print results
# Your code here

Hint

Use depth-first search (DFS) to collect all words starting from the prefix node in the Trie.

Practice

1. Which data structure is generally more efficient for checking if a prefix exists in a large set of strings?

easy

A. Trie, because it stores prefixes explicitly for fast lookup

B. Hash Map, because it stores all strings as keys for quick access

C. Array, because it allows sequential search of prefixes

D. Linked List, because it maintains order of insertion

Solution

1. Step 1: Understand prefix matching requirement

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

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

   Trie stores prefixes explicitly in its nodes, allowing quick traversal to check prefixes. Hash Map stores full strings as keys, so prefix search requires checking multiple keys or extra processing.

3. Final Answer:

   Trie, because it stores prefixes explicitly for fast lookup -> Option A

4. Quick Check:

   Prefix search = Trie [OK]

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

Common Mistakes:

• Thinking hash map keys support prefix search directly
• Confusing prefix search with exact match
• Assuming arrays or linked lists are efficient for prefix search

2. Which of the following is the correct way to insert a word into a Trie node in Python?

easy

A. node[word] = True

B. node.add(word)

C. node[word[i]] = TrieNode()

D. node.children[word[i]] = TrieNode()

Solution

1. Step 1: Understand Trie node structure

   Each Trie node typically has a dictionary called children to store next characters as keys.

2. Step 2: Insert character at position i

   To insert a character, assign a new TrieNode to node.children[word[i]].

3. Final Answer:

   node.children[word[i]] = TrieNode() -> Option D

4. Quick Check:

   Insert char = node.children[word[i]] = TrieNode() [OK]

Hint: Insert chars by assigning new TrieNode to node.children[word[i]] [OK]

Common Mistakes:

• Using node[word] = True for whole word
• Using node[word[i]] = TrieNode() without .children
• Calling non-existent add() method

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

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.end = True
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return True

trie = Trie()
trie.insert('apple')
print(trie.starts_with('app'))
print(trie.starts_with('apl'))

medium

A. False\nFalse

B. True\nFalse

C. True\nTrue

D. False\nTrue

Solution

1. Step 1: Insert 'apple' into Trie

   Each character 'a', 'p', 'p', 'l', 'e' is added as nodes. The end flag is set at 'e'.

2. Step 2: Check starts_with for 'app' and 'apl'

   'app' exists as prefix nodes, so returns True. 'apl' fails at 'l' because 'l' is child of 'p' only after 'pp', so returns False.

3. Final Answer:

   True False -> Option B

4. Quick Check:

   Prefix 'app' found = True, 'apl' not found = False [OK]

Hint: Check prefix nodes exist step-by-step for True/False [OK]

Common Mistakes:

• Assuming 'apl' is prefix of 'apple'
• Confusing end flag with prefix existence
• Mixing up True/False order in output

4. The following code attempts to check if a prefix exists in a hash map of words. What is the main issue?

words = {'apple': 1, 'app': 2, 'banana': 3}
prefix = 'ap'
if prefix in words:
    print('Prefix found')
else:
    print('Prefix not found')

medium

A. The prefix variable is not defined

B. Syntax error in if condition

C. Hash map keys do not support prefix matching directly

D. The print statements are incorrect

Solution

1. Step 1: Understand hash map key lookup

   Checking 'prefix in words' looks for exact key match, not prefix match.

2. Step 2: Identify prefix matching limitation

   Hash maps do not support partial key matching; prefix must be checked by iterating keys or using a Trie.

3. Final Answer:

   Hash map keys do not support prefix matching directly -> Option C

4. Quick Check:

   Prefix search in hash map = no direct support [OK]

Hint: Hash maps need full key match; prefix needs iteration or Trie [OK]

Common Mistakes:

• Thinking 'prefix in dict' checks partial keys
• Assuming syntax error causes failure
• Ignoring need for iteration or Trie for prefix

5. You have a list of 1 million words and want to quickly find all words starting with a given prefix. Which approach is best and why? A) Store all words in a hash map and check each key for prefix match. B) Build a Trie from all words and traverse nodes for the prefix. C) Store words in a list and use list comprehension to filter prefixes. D) Use a linked list to store words and traverse to find prefix matches.

hard

A. Trie allows direct traversal to prefix node, fast for large data

B. Hash map with prefix check on all keys is efficient for large data

C. List comprehension is fastest for prefix search in large data

D. Linked list traversal is best for prefix matching in large data

Solution

1. Step 1: Analyze each data structure for prefix search

   Hash map requires checking all keys for prefix, which is slow for 1 million words. List and linked list require scanning all words, also slow.

2. Step 2: Understand Trie advantage

   Trie stores prefixes as nodes, so traversing to prefix node is fast and does not require scanning all words.

3. Final Answer:

   Trie allows direct traversal to prefix node, fast for large data -> Option A

4. Quick Check:

   Large prefix search = Trie traversal [OK]

Hint: Trie traversal beats scanning all keys for large prefix search [OK]

Common Mistakes:

• Choosing hash map or list for large prefix search
• Ignoring Trie prefix traversal speed
• Assuming linked list is efficient for prefix search