Trie vs Hash Map for Prefix Matching in DSA Python - Visual Comparison

Concept Flow - Trie vs Hash Map for Prefix Matching

Start with empty structure

↓

Insert words one by one

↓

Trie: Create nodes for each char

↓

Mark end of word

↓

Hash Map: Store full words as keys

↓

Store word count or flags

↓

Prefix Query

↓

Trie: Traverse nodes for prefix chars

↓

Collect all words under prefix

↓

Hash Map: Check keys starting with prefix

↓

Return matching words

↓

Result: List of words with prefix

This flow shows how words are inserted and searched by prefix in Trie and Hash Map structures.

Execution Sample

DSA Python

words = ['cat', 'car', 'dog']
trie = {}
for word in words:
    node = trie
    for char in word:
        node = node.setdefault(char, {})
    node['$'] = True

# Search prefix 'ca'
node = trie
for char in 'ca':
    node = node.get(char, None)

Insert words into a Trie and then search for prefix 'ca' by traversing nodes.

Execution Table

Step	Operation	Nodes in Trie	Pointer Changes	Visual State
1	Insert 'cat'	{}	node points to root	{}
2	Insert 'c'	{}	node = root['c'] created	{'c': {}}
3	Insert 'a'	{'c': {}}	node = node['a'] created	{'c': {'a': {}}}
4	Insert 't'	{'c': {'a': {}}}	node = node['t'] created	{'c': {'a': {'t': {}}}}
5	Mark end of 'cat'	{'c': {'a': {'t': {}}}}	node['$'] = True	{'c': {'a': {'t': {'$': True}}}}
6	Insert 'car'	{'c': {'a': {'t': {'$': True}}}}	node = root['c']	{'c': {'a': {'t': {'$': True}}}}
7	Insert 'a' (exists)	{'c': {'a': {'t': {'$': True}}}}	node = node['a']	{'c': {'a': {'t': {'$': True}}}}
8	Insert 'r'	{'c': {'a': {'t': {'$': True}}}}	node['r'] created	{'c': {'a': {'t': {'$': True}, 'r': {}}}}
9	Mark end of 'car'	{'c': {'a': {'t': {'$': True}, 'r': {}}}}	node['$'] = True	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}}
10	Insert 'dog'	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}}	node = root['d'] created	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}, 'd': {}}
11	Insert 'o'	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}, 'd': {}}	node = node['o'] created	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}, 'd': {'o': {}}}
12	Insert 'g'	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}, 'd': {'o': {}}}	node = node['g'] created	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}, 'd': {'o': {'g': {}}}}
13	Mark end of 'dog'	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}, 'd': {'o': {'g': {}}}}	node['$'] = True	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}, 'd': {'o': {'g': {'$': True}}}}
14	Search prefix 'ca'	{...}	node = root['c']	{'c': {...}}
15	Traverse 'a'	{...}	node = node['a']	{'a': {...}}
16	Prefix found, collect words	{...}	Traverse subtree from node	Words: ['cat', 'car']
17	Hash Map store words	Hash Map keys: ['cat', 'car', 'dog']	Store full words as keys	{'cat': True, 'car': True, 'dog': True}
18	Search prefix 'ca' in Hash Map	Hash Map keys	Check keys starting with 'ca'	Matches: ['cat', 'car']
19	End	Final Trie and Hash Map states	No pointer changes	Trie and Hash Map ready for prefix queries

💡 All words inserted and prefix 'ca' searched; prefix matches found in both Trie and Hash Map.

Variable Tracker

Variable	Start	After Step 5	After Step 9	After Step 13	After Step 16	After Step 18	Final
trie	{}	{'c': {'a': {'t': {'$': True}}}}	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}}	{'c': {'a': {'t': {'$': True}, 'r': {'$': True}}}, 'd': {'o': {'g': {'$': True}}}}	Node at 'a' subtree for prefix 'ca'	No change	Final Trie with all words
hash_map	{}	{}	{}	{}	{}	{'cat': True, 'car': True, 'dog': True}	Final Hash Map with all words
node	Points to root	Points to 't' node	Points to 'r' node	Points to 'g' node	Points to 'a' node for prefix	No change	No change

Key Moments - 3 Insights

Why do we need a special end marker ('$') in the Trie nodes?

The '$' marks the end of a complete word in the Trie. Without it, we can't distinguish between a prefix and a full word. For example, 'car' and 'carpet' share nodes, but only nodes with '$' mark full words (see steps 5, 9, 13).

How does prefix search differ between Trie and Hash Map?

Trie traverses nodes character by character for the prefix (steps 14-16), efficiently narrowing down matches. Hash Map checks all keys starting with the prefix (step 18), which can be slower if many keys exist.

Why does Trie use nested dictionaries instead of storing full words?

Trie stores characters in nodes to share prefixes and save space. This structure allows fast prefix queries by traversing nodes. Hash Map stores full words as keys, which is simpler but less efficient for prefix matching.

Visual Quiz - 3 Questions

Look at the execution table at step 5, what does the Trie node for 't' contain?

A An empty dictionary

B A dictionary with end marker '$': True

C A dictionary with child 'r'

D None

💡 Hint

Check the 'Visual State' column at step 5 showing {'t': {'$': True}}

At which step does the Trie first add the word 'car'?

A Step 2

B Step 6

C Step 10

D Step 14

💡 Hint

Look at the 'Operation' column for inserting 'car' starting at step 6

If we add the word 'cap' to the Trie, how would the visual state change after insertion?

A Add a new node 'p' under 'a' with end marker

B Add a new node 'p' under 'r' with end marker

C Add a new node 'p' under 't' with end marker

D No change, word already exists

💡 Hint

New words add nodes under the last matched prefix character, see steps 3-4 for similar insertions

Concept Snapshot

Trie vs Hash Map for Prefix Matching:
- Trie stores words as paths of characters with nodes.
- Uses special end marker ('$') to mark complete words.
- Prefix search traverses nodes for each prefix char.
- Hash Map stores full words as keys.
- Prefix search checks keys starting with prefix.
- Trie is more efficient for large datasets with shared prefixes.

Full Transcript

This lesson compares Trie and Hash Map for prefix matching. We insert words 'cat', 'car', and 'dog' into a Trie by creating nested dictionaries for each character and marking word ends with '$'. The Trie structure shares prefixes, saving space and enabling fast prefix queries by traversing nodes. We also store the same words in a Hash Map as full keys. Searching prefix 'ca' in Trie involves moving through nodes 'c' then 'a' and collecting words below. In Hash Map, we check all keys starting with 'ca'. The Trie is more efficient for prefix queries especially with many words sharing prefixes. Key points include the use of '$' to mark word ends and the difference in search methods. The visual quiz tests understanding of Trie node contents, insertion steps, and how new words affect the Trie structure.

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