Trie vs Hash Map for Prefix Matching in DSA Javascript - Build Both Approaches

Trie vs Hash Map for Prefix Matching

📖 Scenario: You are building a simple search feature for a phone contacts app. Users want to find contacts quickly by typing the first few letters of a name.Two common ways to do this are using a Trie (a tree-like structure) or a Hash Map (a dictionary). This project will help you understand how both work for prefix matching.

🎯 Goal: Build two data structures: a Trie and a Hash Map that store contact names. Then, find all contacts starting with a given prefix using both methods.

📋 What You'll Learn

Create a list of contact names

Create a prefix string to search

Build a Trie data structure and insert all contacts

Build a Hash Map grouping contacts by their prefixes

Write functions to find contacts starting with the prefix using both Trie and Hash Map

Print the results of both searches

💡 Why This Matters

🌍 Real World

Search features in phone contacts, autocomplete in search bars, and prefix-based filtering in apps.

💼 Career

Understanding Trie and Hash Map helps in building efficient search and autocomplete features, common in software engineering roles.

1

Create the contacts list

Create a list called contacts with these exact names: 'Alice', 'Alfred', 'Bob', 'Bobby', 'Charlie'

DSA Javascript

# Create the contacts list
# Your code here

Hint

Use square brackets [] to create a list (array) and include the names as strings.

2

Set the prefix to search

Create a variable called prefix and set it to the string 'Al'

DSA Javascript

const contacts = ['Alice', 'Alfred', 'Bob', 'Bobby', 'Charlie'];
# Create the prefix variable
# Your code here

Hint

Use const prefix = 'Al'; to create the prefix variable.

3

Build Trie and Hash Map for prefix matching

Write a class called TrieNode with a constructor that initializes children as an empty object and isEndOfWord as false. Then write a class called Trie with methods insert(word) to add words and startsWith(prefix) to return all words starting with prefix. Also, create a hashMap object that groups contacts by their first two letters as keys. Insert all contacts into both the Trie and the hashMap.

DSA Javascript

const contacts = ['Alice', 'Alfred', 'Bob', 'Bobby', 'Charlie'];
const prefix = 'Al';
// Define TrieNode and Trie classes
// Create hashMap object
// Insert contacts into Trie and hashMap
# Your code here

Hint

Define TrieNode and Trie classes with the described methods. Use a loop to insert contacts into both data structures.

4

Search and print contacts starting with prefix

Use console.log to print the result of trie.startsWith(prefix) and the result of looking up hashMap[prefix] or an empty list if undefined.

DSA Javascript

const contacts = ['Alice', 'Alfred', 'Bob', 'Bobby', 'Charlie'];
const prefix = 'Al';

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    startsWith(prefix) {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children[char]) {
                return [];
            }
            node = node.children[char];
        }
        const results = [];
        const dfs = (currentNode, path) => {
            if (currentNode.isEndOfWord) {
                results.push(path);
            }
            for (const child in currentNode.children) {
                dfs(currentNode.children[child], path + child);
            }
        };
        dfs(node, prefix);
        return results;
    }
}

const trie = new Trie();
const hashMap = {};

for (const contact of contacts) {
    trie.insert(contact);
    const key = contact.slice(0, 2);
    if (!hashMap[key]) {
        hashMap[key] = [];
    }
    hashMap[key].push(contact);
}

// Print results below
console.log(trie.startsWith(prefix));
console.log(hashMap[prefix] || []);

Hint

Use console.log(trie.startsWith(prefix)) and console.log(hashMap[prefix] || []) to print the matching contacts.