Trie vs Hash Map for Prefix Matching in DSA Go - 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 map[string]bool to store contacts and check prefixes, and another using a Trie data structure for efficient prefix matching.

📋 What You'll Learn

Create a contacts map with exact names

Create a prefix string variable

Implement a function searchWithMap that finds contacts starting with prefix using the map

Implement a Trie with Insert and SearchPrefix methods

Use the Trie to find contacts starting with prefix

Print results from both methods

💡 Why This Matters

🌍 Real World

Searching contacts or words quickly by prefix is common in phone apps, autocomplete, and search engines.

💼 Career

Understanding Tries and hash maps helps in building efficient search features and improves problem-solving skills in coding interviews.

1

Create the contacts map

Create a contacts map of type map[string]bool with these exact entries: "Alice": true, "Bob": true, "Charlie": true, "David": true, "Daniel": true.

DSA Go

# Your code here

Hint

Use map[string]bool and add the exact names as keys with value true.

2

Create the prefix variable

Create a string variable called prefix and set it to "Da".

DSA Go

package main

func main() {
    contacts := map[string]bool{
        "Alice": true,
        "Bob": true,
        "Charlie": true,
        "David": true,
        "Daniel": true,
    }
    // Your code here
}

Hint

Use prefix := "Da" to create the variable.

3

Implement searchWithMap function

Write a function called searchWithMap that takes contacts map[string]bool and prefix string, and returns a []string of contact names starting with prefix. Use a for loop with name to iterate over contacts. Inside the loop, use strings.HasPrefix(name, prefix) to check the prefix and append matching names to a result slice.

DSA Go

package main

import "strings"

func main() {
    contacts := map[string]bool{
        "Alice": true,
        "Bob": true,
        "Charlie": true,
        "David": true,
        "Daniel": true,
    }
    prefix := "Da"

    // Write searchWithMap function below
}

Hint

Use for name := range contacts and strings.HasPrefix(name, prefix) to find matches.

4

Build Trie and print results

Define a TrieNode struct with a children map[rune]*TrieNode and isEnd bool. Implement Insert(word string) and SearchPrefix(prefix string) []string methods on TrieNode. In main, create a root TrieNode, insert all contacts, then call searchWithMap and root.SearchPrefix(prefix). Print the results with fmt.Println as shown: fmt.Println("Map search:", mapResults) and fmt.Println("Trie search:", trieResults).

DSA Go

package main

import "strings"

func searchWithMap(contacts map[string]bool, prefix string) []string {
    var result []string
    for name := range contacts {
        if strings.HasPrefix(name, prefix) {
            result = append(result, name)
        }
    }
    return result
}

func main() {
    contacts := map[string]bool{
        "Alice": true,
        "Bob": true,
        "Charlie": true,
        "David": true,
        "Daniel": true,
    }
    prefix := "Da"

    // Build Trie, insert contacts, search and print results
    // Your code here
}

Hint

Define TrieNode with Insert and SearchPrefix. Insert all contacts, then print results from both methods.