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

Why Trie Exists and What Hash Map Cannot Do for Strings

📖 Scenario: Imagine you are building a search feature for a phone book app. You want to quickly find all contacts whose names start with certain letters. Using a hash map works well for exact names but struggles when you want to find names by prefixes.

🎯 Goal: Build a simple prefix search using a Trie data structure to find all names starting with a given prefix. Understand why a Trie is better than a hash map for prefix queries.

📋 What You'll Learn

Create an array called contacts with these exact names: 'alice', 'alex', 'bob', 'bobby', 'carol'

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

Implement a simple Trie class with insert and startsWith methods

Use the Trie to find all contacts starting with prefix

Print the list of matching contacts

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete features, spell checkers, and IP routing where prefix matching is needed.

💼 Career

Understanding Tries helps in roles involving search engines, text processing, and efficient data retrieval.

1

Create the contacts list

Create an array called contacts with these exact strings: 'alice', 'alex', 'bob', 'bobby', 'carol'

DSA Typescript

// Create the contacts array
// Your code here

Hint

Use const contacts = ['alice', 'alex', 'bob', 'bobby', 'carol'];

2

Set the prefix to search

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

DSA Typescript

const contacts = ['alice', 'alex', 'bob', 'bobby', 'carol'];
// Create the prefix variable
// Your code here

Hint

Use const prefix = 'bo';

3

Implement the Trie class with insert and startsWith

Create a class called Trie with methods insert(word: string): void and startsWith(prefix: string): string[]. The insert method adds a word to the Trie. The startsWith method returns all words in the Trie that start with the given prefix.

DSA Typescript

const contacts = ['alice', 'alex', 'bob', 'bobby', 'carol'];
const prefix = 'bo';
// Implement the Trie class with insert and startsWith methods
// Your code here

Hint

Define a Trie class with insert and startsWith methods. Use a Map to store children nodes.

4

Find and print contacts starting with the prefix

Use the startsWith method of the trie object to find all contacts starting with prefix. Print the resulting array.

DSA Typescript

const contacts = ['alice', 'alex', 'bob', 'bobby', 'carol'];
const prefix = 'bo';

class TrieNode {
    children: Map = new Map();
    isEndOfWord: boolean = false;
}

class Trie {
    root: TrieNode;

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

    insert(word: string): void {
        let node = this.root;
        for (const char of word) {
            if (!node.children.has(char)) {
                node.children.set(char, new TrieNode());
            }
            node = node.children.get(char)!;
        }
        node.isEndOfWord = true;
    }

    startsWith(prefix: string): string[] {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children.has(char)) {
                return [];
            }
            node = node.children.get(char)!;
        }
        const results: string[] = [];
        this.collectAllWords(node, prefix, results);
        return results;
    }

    private collectAllWords(node: TrieNode, prefix: string, results: string[]): void {
        if (node.isEndOfWord) {
            results.push(prefix);
        }
        for (const [char, childNode] of node.children) {
            this.collectAllWords(childNode, prefix + char, results);
        }
    }
}

const trie = new Trie();
for (const contact of contacts) {
    trie.insert(contact);
}
// Print the contacts starting with prefix
// Your code here

Hint

Call trie.startsWith(prefix) and print the result using console.log.