Why Trie Exists and What Hash Map Cannot Do for Strings in DSA Go - See It Work

Why Trie Exists and What Hash Map Cannot Do for Strings

📖 Scenario: Imagine you are building a phone contact app. You want to store many names and quickly find all contacts starting with certain letters. Using a hash map can find exact names fast, but it cannot help find names by prefix efficiently.We will build a simple example to see why a Trie is useful and what a hash map cannot do well with strings.

🎯 Goal: Build a small program to store a list of words in a hash map and then try to find all words starting with a prefix. Then, see why this is hard with a hash map and how a Trie can help.

📋 What You'll Learn

Create a hash map with given words

Create a prefix string variable

Write code to find words starting with the prefix using the hash map

Print the found words

💡 Why This Matters

🌍 Real World

Phone contact apps, autocomplete features, and search engines need fast prefix search for strings.

💼 Career

Understanding why Tries are used helps in roles involving search optimization, text processing, and building efficient data retrieval systems.

1

Create a hash map with words

Create a variable called wordsMap of type map[string]bool and add these exact words as keys with value true: "apple", "app", "banana", "bat", "bath".

DSA Go

# Your code here

Hint

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

2

Create a prefix variable

Create a variable called prefix of type string and set it to the exact value "ba".

DSA Go

package main

func main() {
    wordsMap := map[string]bool{
        "apple": true,
        "app": true,
        "banana": true,
        "bat": true,
        "bath": true,
    }
    // Your code here
}

Hint

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

3

Find words starting with prefix using hash map

Use a for loop with variable word to iterate over wordsMap keys. Inside the loop, use strings.HasPrefix(word, prefix) to check if word starts with prefix. If yes, append word to a slice called foundWords of type []string. Initialize foundWords as an empty slice before the loop.

DSA Go

package main

import "strings"

func main() {
    wordsMap := map[string]bool{
        "apple": true,
        "app": true,
        "banana": true,
        "bat": true,
        "bath": true,
    }
    prefix := "ba"
    // Your code here
}

Hint

Initialize foundWords as an empty slice. Loop over wordsMap keys. Use strings.HasPrefix to check prefix and append matching words.

4

Print the found words

Use fmt.Println(foundWords) to print the slice foundWords. Import fmt package at the top.

DSA Go

package main

import "strings"

func main() {
    wordsMap := map[string]bool{
        "apple": true,
        "app": true,
        "banana": true,
        "bat": true,
        "bath": true,
    }
    prefix := "ba"
    foundWords := []string{}
    for word := range wordsMap {
        if strings.HasPrefix(word, prefix) {
            foundWords = append(foundWords, word)
        }
    }
    // Your code here
}

Hint

Use fmt.Println(foundWords) to print the list of words starting with the prefix.