Trie vs Hash Map for Prefix Matching in DSA Python - Trade-offs & Analysis

Mental Model

A trie stores words by shared prefixes in a tree, while a hash map stores whole words as keys. Tries let you find all words starting with a prefix quickly, hash maps do not.

Analogy: Imagine a phone book organized by first letters and then next letters (trie), versus a list of names with their phone numbers (hash map). To find all names starting with 'Al', the phone book groups them together, but the list needs to check every name.

Trie:
root
 ↓
 a -> l -> l -> null
       ↓
       i -> c -> e -> null

Hash Map:
{
  "alice": number,
  "all": number
}

Dry Run Walkthrough

Input: words: ["all", "alice", "bob"], prefix: "al"

Goal: Find all words starting with prefix "al" using trie and hash map

Step 1: Insert "all" into trie by creating nodes for 'a', 'l', 'l'

root -> a -> l -> l [end]
Hash Map: {"all": true}

Why: Build trie nodes for each letter to represent the word

Step 2: Insert "alice" into trie by adding nodes 'i', 'c', 'e' after 'l'

root -> a -> l -> l [end]
           ↓
           i -> c -> e [end]
Hash Map: {"all": true, "alice": true}

Why: Extend trie to include new word sharing prefix 'al'

Step 3: Insert "bob" into trie by creating nodes 'b', 'o', 'b' from root

root -> a -> l -> l [end]
           ↓
           i -> c -> e [end]
root -> b -> o -> b [end]
Hash Map: {"all": true, "alice": true, "bob": true}

Why: Add new branch for word with different prefix

Step 4: Search trie for prefix "al" by following nodes 'a' then 'l'

At node 'l' after 'a' -> 'l'
Words found: "all", "alice"

Why: Traverse trie to prefix end to find all words below

Step 5: Search hash map keys for prefix "al" by checking each key

Check "all" (matches), "alice" (matches), "bob" (no)
Words found: "all", "alice"

Why: Hash map requires scanning all keys to find prefix matches

Result:

Trie structure:
root -> a -> l -> l [end]
           ↓
           i -> c -> e [end]
root -> b -> o -> b [end]
Words with prefix 'al': all, alice
Hash Map keys: all, alice, bob
Words with prefix 'al': all, alice

Annotated Code

DSA Python

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

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()  # create node if missing
            node = node.children[char]  # move to child node
        node.is_end = True  # mark end of word

    def starts_with(self, prefix: str) -> list:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []  # prefix not found
            node = node.children[char]  # move to next node
        result = []
        self._dfs(node, prefix, result)  # collect all words below prefix
        return result

    def _dfs(self, node, path, result):
        if node.is_end:
            result.append(path)  # found a word
        for char, child in node.children.items():
            self._dfs(child, path + char, result)  # explore children


def prefix_match_hashmap(words, prefix):
    return [word for word in words if word.startswith(prefix)]

# Driver code
words = ["all", "alice", "bob"]
prefix = "al"

# Using Trie
trie = Trie()
for w in words:
    trie.insert(w)
trie_result = trie.starts_with(prefix)

# Using Hash Map (dictionary keys)
hash_map = {w: True for w in words}
hash_result = prefix_match_hashmap(list(hash_map.keys()), prefix)

print("Trie words with prefix '" + prefix + "':", ", ".join(trie_result))
print("Hash Map words with prefix '" + prefix + "':", ", ".join(hash_result))

if char not in node.children: node.children[char] = TrieNode() # create node if missing

create new trie node for missing character to build prefix path

node = node.children[char] # move to child node

advance current node to next character node

node.is_end = True # mark end of word

mark node as end of a valid word

if char not in node.children: return [] # prefix not found

stop search if prefix character missing

self._dfs(node, prefix, result) # collect all words below prefix

collect all words starting with prefix by depth-first search

return [word for word in words if word.startswith(prefix)]

filter all words in hash map keys by prefix match

Output

Trie words with prefix 'al': all, alice

Hash Map words with prefix 'al': all, alice

Complexity Analysis

Time: O(m + k) where m is length of prefix and k is number of words with prefix for trie; O(n * p) for hash map where n is total words and p is prefix length because it checks each word

Space: O(total characters in all words) for trie due to nodes; O(n) for hash map storing all words

vs Alternative: Trie is faster for prefix queries because it avoids scanning all words; hash map is simpler but slower for prefix matching

Edge Cases

empty word list

both trie and hash map return empty list for any prefix

DSA Python

if char not in node.children:
    return []  # prefix not found

prefix not present in any word

both return empty list quickly

DSA Python

if char not in node.children:
    return []  # prefix not found

words with shared prefix but different lengths

trie correctly returns all matching words; hash map filters correctly

DSA Python

node.is_end = True  # mark end of word

When to Use This Pattern

When a problem asks for fast prefix searches or autocomplete, reach for the trie pattern because it organizes words by shared prefixes for quick lookup.

Common Mistakes

Mistake: Using hash map keys directly for prefix matching without scanning all keys
Fix: Implement a loop to check each key's prefix or use a trie for efficient prefix queries

Mistake: Not marking end of word in trie nodes, causing incorrect word detection
Fix: Set is_end = True at the last node of each inserted word

Summary

Compares trie and hash map for finding words by prefix.

Use trie when you need fast prefix-based searches over many words.

Trie stores words by shared prefixes, enabling quick prefix queries without scanning all words.

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