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

Mental Model

A trie stores words by their letters in a tree, making prefix search fast. A hash map stores whole words as keys, so prefix search needs extra work.

Analogy: Imagine a phone book organized by first letter, then second letter, and so on (trie), versus a list of names where you check each name fully (hash map).

Trie:
root
 ↓
 a -> p -> p -> l -> e
        ↓
        r
Hash Map:
{ "apple": true, "app": true, "apricot": true }

Dry Run Walkthrough

Input: words: ["app", "apple", "apricot"], prefix: "app"

Goal: Find all words starting with prefix "app" efficiently

Step 1: Insert "app" into trie by creating nodes for 'a', 'p', 'p'

root -> a -> p -> p [end]
Hash Map: { }

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

Step 2: Insert "apple" by extending from existing 'app' nodes with 'l' and 'e'

root -> a -> p -> p -> l -> e [end]
Hash Map: { }

Why: Reuse existing prefix nodes, add new nodes for remaining letters

Step 3: Insert "apricot" by branching from 'a' node with 'p', 'r', 'i', 'c', 'o', 't'

root -> a -> p -> p -> l -> e [end]
           ↓
           r -> i -> c -> o -> t [end]
Hash Map: { }

Why: Create new branch for different word starting with 'ap'

Step 4: Search prefix "app" in trie by following nodes 'a' -> 'p' -> 'p'

At node 'p' (second 'p')
Words below: "app", "apple"
Hash Map: { }

Why: Traverse trie nodes matching prefix letters to reach prefix node

Step 5: Collect all words below prefix node: "app", "apple"

Result: ["app", "apple"]
Hash Map: { }

Why: Gather all words that share the prefix from trie subtree

Step 6: Search prefix "app" in hash map by checking each key if it starts with "app"

Check keys: "app" (yes), "apple" (yes), "apricot" (no)
Result: ["app", "apple"]

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

Result:

Trie final state:
root -> a -> p -> p -> l -> e [end]
           ↓
           r -> i -> c -> o -> t [end]
Prefix "app" matches: ["app", "apple"]
Hash Map final state:
{ "app": true, "apple": true, "apricot": true }
Prefix "app" matches: ["app", "apple"]

Annotated Code

DSA C++

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>

using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEnd = false;
};

class Trie {
public:
    TrieNode* root;
    Trie() { root = new TrieNode(); }

    void insert(const string& word) {
        TrieNode* curr = root;
        for (char c : word) {
            if (curr->children.find(c) == curr->children.end()) {
                curr->children[c] = new TrieNode();
            }
            curr = curr->children[c]; // advance curr to next node
        }
        curr->isEnd = true; // mark end of word
    }

    void dfs(TrieNode* node, string prefix, vector<string>& results) {
        if (node->isEnd) results.push_back(prefix); // collect word
        for (auto& pair : node->children) {
            dfs(pair.second, prefix + pair.first, results); // explore children
        }
    }

    vector<string> startsWith(const string& prefix) {
        TrieNode* curr = root;
        for (char c : prefix) {
            if (curr->children.find(c) == curr->children.end()) return {};
            curr = curr->children[c]; // advance curr to prefix node
        }
        vector<string> results;
        dfs(curr, prefix, results); // collect all words below prefix
        return results;
    }
};

vector<string> prefixMatchHashMap(const unordered_map<string, bool>& map, const string& prefix) {
    vector<string> results;
    for (const auto& pair : map) {
        if (pair.first.compare(0, prefix.size(), prefix) == 0) {
            results.push_back(pair.first); // add matching keys
        }
    }
    return results;
}

int main() {
    vector<string> words = {"app", "apple", "apricot"};
    string prefix = "app";

    Trie trie;
    for (const string& w : words) {
        trie.insert(w); // build trie
    }

    unordered_map<string, bool> map;
    for (const string& w : words) {
        map[w] = true; // build hash map
    }

    vector<string> trieResults = trie.startsWith(prefix);
    cout << "Trie prefix matches: ";
    for (const string& w : trieResults) cout << w << " ";
    cout << endl;

    vector<string> mapResults = prefixMatchHashMap(map, prefix);
    cout << "Hash Map prefix matches: ";
    for (const string& w : mapResults) cout << w << " ";
    cout << endl;

    return 0;
}

curr = curr->children[c]; // advance curr to next node

advance curr to next node to build or traverse trie

curr->isEnd = true; // mark end of word

mark current node as end of a valid word

if (curr->children.find(c) == curr->children.end()) return {};

stop search if prefix letter not found

dfs(curr, prefix, results); // collect all words below prefix

collect all words starting with prefix from trie subtree

if (pair.first.compare(0, prefix.size(), prefix) == 0) {

check if hash map key starts with prefix

Output

Trie prefix matches: app apple 

Hash Map prefix matches: app apple 

Complexity Analysis

Time: Trie: O(m + k) where m is prefix length and k is number of matched words; Hash Map: O(n * m) where n is number of keys and m is prefix length because each key is checked

Space: Trie: O(total letters in all words) for nodes; Hash Map: O(n) for storing all keys

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

Edge Cases

Empty prefix string

Trie returns all words; hash map returns all keys

DSA C++

if (curr->children.find(c) == curr->children.end()) return {};

Prefix not present in any word

Both return empty list

DSA C++

if (curr->children.find(c) == curr->children.end()) return {};

Words with shared prefixes

Trie shares nodes efficiently; hash map stores full keys separately

DSA C++

curr = curr->children[c]; // advance curr to next node

When to Use This Pattern

When you need to find all words starting with a prefix quickly, use a trie because it organizes words by letters, unlike a hash map which stores whole words and requires scanning all keys.

Common Mistakes

Mistake: Trying to do prefix search directly on hash map keys 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 prefix matches
Fix: Set isEnd = true at the last node of each inserted word

Summary

Compares trie and hash map for finding words by prefix.

Use trie for fast prefix search; hash map for exact word lookup.

Trie stores words letter by letter, enabling quick prefix traversal.

Practice

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

easy

A. Linked List, because it stores elements in order

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

C. Array, because it allows sequential search of prefixes

D. Trie, because it stores prefixes explicitly and allows fast prefix search

Solution

1. Step 1: Understand prefix search requirements

   Prefix search needs to quickly find if any string starts with a given prefix.

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

   Trie stores prefixes explicitly, allowing fast traversal to check prefixes. Hash Map stores full keys, so prefix search requires checking many keys or extra processing.

3. Final Answer:

   Trie, because it stores prefixes explicitly and allows fast prefix search -> Option D

4. Quick Check:

   Prefix search = Trie [OK]

Hint: Prefix search is fastest with Trie due to explicit prefix nodes [OK]

Common Mistakes:

• Thinking hash map can do prefix search in constant time
• Confusing prefix search with exact key search
• Ignoring the need to check multiple keys in hash map

2. Which of the following is the correct way to declare a Trie node in C++ for lowercase English letters?

easy

A. struct TrieNode { TrieNode* children[26]; bool isEnd; };

B. struct TrieNode { map children; bool isEnd; };

C. struct TrieNode { vector<int> children; bool isEnd; };

D. struct TrieNode { unordered_map children; bool isEnd; };

Solution

1. Step 1: Identify correct children type for fixed alphabet

   For lowercase English letters, fixed size array of 26 pointers is efficient.

2. Step 2: Check each option's children type

   struct TrieNode { TrieNode* children[26]; bool isEnd; }; uses TrieNode* children[26], which is correct. struct TrieNode { map children; bool isEnd; }; uses map, which is valid but slower. Options A and C use incorrect types.

3. Final Answer:

   struct TrieNode { TrieNode* children[26]; bool isEnd; }; -> Option A

4. Quick Check:

   Fixed alphabet Trie node = array of 26 pointers [OK]

Hint: Use array of 26 pointers for fixed lowercase letters [OK]

Common Mistakes:

• Using vector<int> instead of pointers for children
• Using unordered_map with wrong key type
• Confusing map with array for fixed alphabets

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

struct TrieNode {
  TrieNode* children[26] = {nullptr};
  bool isEnd = false;
};

TrieNode* root = new TrieNode();

// Insert "cat"
string word = "cat";
TrieNode* node = root;
for (char c : word) {
  int index = c - 'a';
  if (!node->children[index])
    node->children[index] = new TrieNode();
  node = node->children[index];
}
node->isEnd = true;

// Check prefix "ca"
node = root;
string prefix = "ca";
bool found = true;
for (char c : prefix) {
  int index = c - 'a';
  if (!node->children[index]) {
    found = false;
    break;
  }
  node = node->children[index];
}
cout << (found ? "Prefix exists" : "Prefix not found") << endl;

medium

A. Prefix exists

B. Prefix not found

C. Compilation error

D. Runtime error

Solution

1. Step 1: Insert "cat" into Trie

   Each character 'c', 'a', 't' creates nodes if missing. After insertion, path for "cat" exists.

2. Step 2: Check prefix "ca"

   Traverse nodes for 'c' and 'a'. Both nodes exist, so prefix is found.

3. Final Answer:

   Prefix exists -> Option A

4. Quick Check:

   Inserted "cat" contains prefix "ca" [OK]

Hint: Traverse nodes for prefix; if all exist, prefix exists [OK]

Common Mistakes:

• Assuming prefix must be a full word
• Forgetting to check each character node
• Confusing isEnd with prefix existence

4. Identify the bug in this C++ Trie prefix search code snippet:

bool startsWith(TrieNode* root, const string& prefix) {
  TrieNode* node = root;
  for (char c : prefix) {
    int idx = c - 'a';
    if (node->children[idx] == nullptr)
      return false;
    node = node->children[idx];
  }
  return node->isEnd;
}

medium

A. Index calculation is wrong, should be c - 'A'

B. Should return true after loop, not node->isEnd

C. Missing null check for root pointer

D. Loop should iterate over root->children, not prefix

Solution

1. Step 1: Understand prefix search logic

   Prefix search should return true if all prefix nodes exist, regardless of isEnd.

2. Step 2: Identify incorrect return statement

   Returning node->isEnd checks if prefix is a full word, not just a prefix. It should return true after loop.

3. Final Answer:

   Should return true after loop, not node->isEnd -> Option B

4. Quick Check:

   Prefix search returns true if prefix nodes exist [OK]

Hint: Prefix search returns true if path exists, ignore isEnd [OK]

Common Mistakes:

• Confusing prefix existence with full word existence
• Incorrect index calculation for characters
• Not checking for null root pointer

5. You need to implement a system that supports fast prefix matching for millions of strings with dynamic insertions and lookups. Which approach is best and why? Option A: Use a sorted array of strings and binary search for prefixes. Option B: Use a Hash Map storing all strings and check prefixes by scanning keys. Option C: Use a Trie for prefix matching. Option D: Use a linked list of strings and linear search for prefixes.

hard

A. Sorted array, because binary search is fast for prefix queries

B. Hash Map, because it has constant time lookup for exact keys

C. Trie, because it provides efficient prefix search and dynamic insertions

D. Linked list, because it is simple to implement

Solution

1. Step 1: Analyze requirements for millions of strings with dynamic insertions

   Dynamic insertions require efficient updates; prefix matching needs fast queries.

2. Step 2: Compare data structures for prefix matching and insertions

   Trie supports fast prefix search and efficient insertions. Hash Map is fast for exact keys but slow for prefix. Sorted array requires costly insertions. Linked list is slow for both.

3. Final Answer:

   Trie, because it provides efficient prefix search and dynamic insertions -> Option C

4. Quick Check:

   Dynamic prefix search = Trie [OK]

Hint: For dynamic prefix search, Trie beats hash map and arrays [OK]

Common Mistakes:

• Choosing hash map for prefix search without scanning keys
• Ignoring insertion cost in sorted arrays
• Underestimating linked list search time