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

Mental Model

A trie stores words by their letters step-by-step, making prefix search fast. A hash map stores whole words as keys, so prefix search needs checking many keys.

Analogy: Imagine a library organized by shelves for each letter (trie), so you quickly find all books starting with 'A'. A hash map is like a pile of books with labels; to find all starting with 'A', you check each label one by one.

Trie:
root
 ↓
 a -> p -> p -> l -> e
     ↓
     r -> t

Hash Map:
{ "apple": true, "app": true, "art": true }

Dry Run Walkthrough

Input: words: ["app", "apple", "art"], prefix: "ap"

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

Step 1: Insert "app" into trie letter by letter

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

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

Step 2: Insert "apple" into trie continuing from "app"

root -> a -> p -> p -> l -> e [end]
Hash Map: {"app": true, "apple": true}

Why: Extend trie nodes for new letters after existing prefix

Step 3: Insert "art" into trie starting from root

root -> a -> p -> p -> l -> e [end]
       ↓
       r -> t [end]
Hash Map: {"app": true, "apple": true, "art": true}

Why: Add new branch for different prefix starting with 'a'

Step 4: Search trie for prefix "ap" by following nodes a -> p

At node 'p' after root -> a -> p
Hash Map: keys checked one by one

Why: Reach prefix node to collect all words below

Step 5: Collect all words under trie node 'p': "app", "apple"

Found words: "app", "apple"
Hash Map: check keys starting with "ap"

Why: Trie allows direct access to prefix subtree

Step 6: In hash map, check each key if it starts with "ap"

Keys: "app" (yes), "apple" (yes), "art" (no)
Found words: "app", "apple"

Why: Hash map needs to scan all keys for prefix match

Result:

Trie words with prefix 'ap': app -> apple
Hash Map words with prefix 'ap': app, apple

Annotated Code

DSA Go

package main

import (
	"fmt"
)

// TrieNode represents each node in the trie
type TrieNode struct {
	children map[rune]*TrieNode
	isEnd    bool
}

// Trie structure with root node
type Trie struct {
	root *TrieNode
}

// NewTrie creates a new empty trie
func NewTrie() *Trie {
	return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}

// Insert adds a word to the trie
func (t *Trie) Insert(word string) {
	curr := t.root
	for _, ch := range word {
		if curr.children[ch] == nil {
			curr.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
		}
		curr = curr.children[ch] // advance curr to next node
	}
	curr.isEnd = true // mark end of word
}

// collectWords collects all words under given node with prefix
func (t *Trie) collectWords(node *TrieNode, prefix string, results *[]string) {
	if node.isEnd {
		*results = append(*results, prefix) // found a word
	}
	for ch, child := range node.children {
		t.collectWords(child, prefix+string(ch), results) // recurse children
	}
}

// StartsWith finds all words starting with prefix
func (t *Trie) StartsWith(prefix string) []string {
	curr := t.root
	for _, ch := range prefix {
		if curr.children[ch] == nil {
			return []string{} // prefix not found
		}
		curr = curr.children[ch] // advance curr to prefix node
	}
	results := []string{}
	t.collectWords(curr, prefix, &results) // collect all words below prefix
	return results
}

func main() {
	words := []string{"app", "apple", "art"}
	prefix := "ap"

	// Build trie
	trie := NewTrie()
	for _, w := range words {
		trie.Insert(w)
	}

	// Search trie
	trieResults := trie.StartsWith(prefix)
	fmt.Print("Trie words with prefix '", prefix, "': ")
	for i, w := range trieResults {
		if i > 0 {
			fmt.Print(" -> ")
		}
		fmt.Print(w)
	}
	fmt.Println()

	// Hash map approach
	hashMap := make(map[string]bool)
	for _, w := range words {
		hashMap[w] = true
	}

	fmt.Print("Hash Map words with prefix '", prefix, "': ")
	first := true
	for k := range hashMap {
		if len(k) >= len(prefix) && k[:len(prefix)] == prefix {
			if !first {
				fmt.Print(", ")
			}
			fmt.Print(k)
			first = false
		}
	}
	fmt.Println()
}

curr = curr.children[ch] // advance curr to next node

advance curr to next node -- build path for word

curr.isEnd = true // mark end of word

mark node as end of a valid word

if curr.children[ch] == nil { return []string{} }

stop if prefix path missing

curr = curr.children[ch] // advance curr to prefix node

follow prefix path in trie

t.collectWords(curr, prefix, &results) // collect all words below prefix

gather all words starting with prefix

for k := range hashMap { if len(k) >= len(prefix) && k[:len(prefix)] == prefix { ... } }

check each key for prefix match in hash map

Output

Trie words with prefix 'ap': app -> apple

Hash Map words with prefix 'ap': 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 words 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 words as keys

vs Alternative: Trie is faster for prefix queries because it directly follows prefix nodes; hash map is slower as it scans all keys for prefix matches

Edge Cases

Empty word list

Trie remains empty; prefix search returns empty list; hash map is empty

DSA Go

if curr.children[ch] == nil { return []string{} }

Prefix not present in any word

Trie search returns empty list immediately; hash map finds no keys starting with prefix

DSA Go

if curr.children[ch] == nil { return []string{} }

Words with shared prefixes

Trie shares nodes for common prefix letters; hash map stores all keys separately

DSA Go

curr = curr.children[ch] // advance curr to next node

When to Use This Pattern

When a problem asks for fast prefix search or autocomplete, reach for the trie pattern because it stores words letter-by-letter allowing quick prefix traversal, unlike hash maps which require scanning all keys.

Common Mistakes

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

Summary

Compares trie and hash map for finding words by prefix.

Use trie when you need fast prefix search; use hash map for exact word lookup.

Trie stores words letter-by-letter enabling direct prefix traversal; hash map stores whole words requiring full key scans for prefix.

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 allows sequential access to elements

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

C. Array, because it stores elements in order and allows binary search

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 is good for exact key lookup but not for prefix matching.

3. Final Answer:

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

4. Quick Check:

   Prefix search = Trie [OK]

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

Common Mistakes:

• Thinking hash map supports prefix search efficiently
• Confusing prefix search with exact key lookup
• Assuming arrays or lists are efficient for prefix matching

2. Which of the following is the correct way to declare a Trie node struct in Go for prefix matching?

easy

A. type TrieNode struct { next map[string]int; end bool }

B. type TrieNode struct { children map[rune]*TrieNode; isEnd bool }

C. type TrieNode struct { children []int; isEnd string }

D. type TrieNode struct { children map[int]string; isEnd int }

Solution

1. Step 1: Identify correct field types for TrieNode

   Children should map characters (rune) to TrieNode pointers; isEnd is a boolean indicating word end.

2. Step 2: Check each option's correctness

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } uses map[rune]*TrieNode and bool for isEnd, which is correct. Others have wrong types or field names.

3. Final Answer:

   type TrieNode struct { children map[rune]*TrieNode; isEnd bool } -> Option B

4. Quick Check:

   TrieNode struct with map[rune]*TrieNode and bool isEnd = type TrieNode struct { children map[rune]*TrieNode; isEnd bool } [OK]

Hint: Trie children map keys are runes, isEnd is bool [OK]

Common Mistakes:

• Using incorrect types for children map keys or values
• Using string instead of bool for isEnd
• Confusing field names or types

3. Given the following Go code snippet using a Trie for prefix matching, what will be the output?

type TrieNode struct {
    children map[rune]*TrieNode
    isEnd    bool
}

func (t *TrieNode) Insert(word string) {
    node := t
    for _, ch := range word {
        if node.children[ch] == nil {
            node.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (t *TrieNode) StartsWith(prefix string) bool {
    node := t
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return true
}

func main() {
    root := &TrieNode{children: make(map[rune]*TrieNode)}
    root.Insert("cat")
    root.Insert("car")
    root.Insert("dog")
    fmt.Println(root.StartsWith("ca"))
    fmt.Println(root.StartsWith("do"))
    fmt.Println(root.StartsWith("bat"))
}

medium

A. true
true
false

B. false
true
false

C. true
false
false

D. false
false
true

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted, building paths for 'c'->'a'->'t', 'c'->'a'->'r', and 'd'->'o'->'g'.

2. Step 2: Check StartsWith calls

   StartsWith("ca") returns true because 'c'->'a' path exists. StartsWith("do") returns true because 'd'->'o' path exists. StartsWith("bat") returns false because 'b' path does not exist.

3. Final Answer:

   true true false -> Option A

4. Quick Check:

   Prefix "ca" and "do" found, "bat" not found = true true false [OK]

Hint: Check if prefix path exists in Trie for true/false [OK]

Common Mistakes:

• Assuming StartsWith returns true only if full word exists
• Confusing Insert with StartsWith behavior
• Ignoring that 'bat' prefix is missing

4. The following Go code attempts to check if a prefix exists using a Hash Map of strings to booleans. What is the main issue?

func PrefixExists(words map[string]bool, prefix string) bool {
    for word := range words {
        if strings.HasPrefix(word, prefix) {
            return true
        }
    }
    return false
}

func main() {
    words := map[string]bool{"apple": true, "app": true, "banana": true}
    fmt.Println(PrefixExists(words, "ap"))
}

medium

A. Inefficient for large datasets due to linear scan over all keys

B. Syntax error: strings.HasPrefix is not a valid function

C. Incorrect return type: should return string instead of bool

D. Map keys cannot be iterated in Go

Solution

1. Step 1: Analyze PrefixExists function logic

   The function iterates over all keys in the map and checks prefix using strings.HasPrefix.

2. Step 2: Identify performance issue

   Iterating all keys causes linear time complexity, which is inefficient for large datasets compared to Trie prefix search.

3. Final Answer:

   Inefficient for large datasets due to linear scan over all keys -> Option A

4. Quick Check:

   Linear scan in map for prefix = inefficient [OK]

Hint: Hash map prefix check needs full scan, slow for many keys [OK]

Common Mistakes:

• Thinking strings.HasPrefix is invalid
• Assuming map iteration is not allowed
• Confusing return types

5. You need to design a system to quickly find all words starting with a given prefix from a dictionary of 1 million words. Which approach is best and why? A) Use a Hash Map storing all words as keys and scan keys for prefix matches. B) Use a Trie to store all words and traverse nodes to find prefix matches. C) Store words in a sorted array and use binary search to find prefix range. D) Use a Linked List to store words and iterate to find prefix matches.

hard

A. Sorted array with binary search finds prefix range efficiently

B. Hash Map with linear scan is fast due to constant lookup

C. Trie allows efficient prefix traversal without scanning all words

D. Linked List is best for sequential prefix matching

Solution

1. Step 1: Evaluate each data structure for prefix search on large data

   Hash Map requires scanning all keys for prefix, inefficient. Trie is efficient and allows prefix traversal without scanning all words. Sorted array allows binary search to find prefix range quickly but requires additional steps to find all matches.

2. Step 2: Compare Trie and sorted array for large datasets

   Trie uses more memory but provides direct prefix traversal and efficient prefix queries. Sorted array with binary search is efficient for prefix range queries but retrieving all matches requires scanning the range.

3. Final Answer:

   Trie allows efficient prefix traversal without scanning all words -> Option C

4. Quick Check:

   Trie prefix traversal = efficient prefix search [OK]

Hint: Trie allows direct prefix traversal for fast prefix search [OK]

Common Mistakes:

• Choosing sorted array without considering retrieval cost
• Assuming hash map supports fast prefix search
• Ignoring Trie advantages for prefix queries