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

Trie vs Hash Map for Prefix Matching

📖 Scenario: You are building a simple search feature for a phone contact list. 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 to store and find names by their prefixes using both methods.

🎯 Goal: You will create a list of contact names, set up a prefix to search for, then write code to find all contacts starting with that prefix using a Hash Map and a Trie. Finally, you will print the matching contacts.

📋 What You'll Learn

Create a list of contact names exactly as given

Create a prefix string variable to search

Write a function to find contacts starting with the prefix using a Hash Map

Write a Trie class with insert and prefix search methods

Use the Trie to find contacts starting with the prefix

Print the results from both methods

💡 Why This Matters

🌍 Real World

Prefix matching is used in search bars, autocomplete features, and contact lists to quickly find items starting with typed letters.

💼 Career

Understanding Tries and Hash Maps helps in building efficient search features and is a common topic in coding interviews.

1

Create the contact list

Create a variable called contacts as an array of strings with these exact names: 'Alice', 'Bob', 'Alfred', 'Bobby', 'Albert'

DSA Typescript

// Create the contacts array with the exact names
// Your code here

Hint

Use square brackets to create an array and include the names as strings separated by commas.

2

Set the prefix to search

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

DSA Typescript

const contacts: string[] = ['Alice', 'Bob', 'Alfred', 'Bobby', 'Albert'];
// Create the prefix string 'Al'
// Your code here

Hint

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

3

Find contacts with prefix using Hash Map

Write a function called findWithHashMap that takes contacts and prefix as parameters and returns an array of contacts starting with prefix. Use a for loop to check each contact with startsWith method.

DSA Typescript

const contacts: string[] = ['Alice', 'Bob', 'Alfred', 'Bobby', 'Albert'];
const prefix: string = 'Al';

// Write function findWithHashMap
// Your code here

Hint

Use a loop from 0 to contacts.length and check if each contact starts with prefix. If yes, add it to result array.

4

Build Trie and print results

Define a class TrieNode with a children map and isEnd boolean. Define a class Trie with insert and startsWith methods. Insert all contacts into the Trie. Use startsWith to find contacts starting with prefix. Then print the results from findWithHashMap and Trie search using console.log.

DSA Typescript

const contacts: string[] = ['Alice', 'Bob', 'Alfred', 'Bobby', 'Albert'];
const prefix: string = 'Al';

function findWithHashMap(contacts: string[], prefix: string): string[] {
    const result: string[] = [];
    for (let i = 0; i < contacts.length; i++) {
        if (contacts[i].startsWith(prefix)) {
            result.push(contacts[i]);
        }
    }
    return result;
}

// Define TrieNode and Trie classes
// Insert contacts into Trie
// Find contacts with prefix using Trie
// Print results from both methods
// Your code here

Hint

Build the Trie by inserting each contact. Use a helper DFS function to collect all words starting with the prefix. Print both results arrays.