Word Search in Trie in DSA Typescript - Build from Scratch

Word Search in Trie

📖 Scenario: You are building a simple word search tool that can quickly check if a word exists in a collection. To do this efficiently, you will use a Trie data structure, which stores words in a tree-like format.Imagine a phone contact list where you want to find if a name exists by typing letters one by one. The Trie helps you find matches fast.

🎯 Goal: Create a Trie to store a list of words, then write a function to search if a given word exists in the Trie.

📋 What You'll Learn

Create a TrieNode class with a children map and an end-of-word flag

Create a Trie class with insert and search methods

Insert given words into the Trie

Search for a specific word in the Trie and return true if found, false otherwise

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete features, spell checkers, and search engines to quickly find words or prefixes.

💼 Career

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

1

Create TrieNode class

Create a class called TrieNode with a property children initialized as an empty Map<string, TrieNode> and a boolean property isEndOfWord set to false.

DSA Typescript

// Your code here

Hint

Use Map to store children nodes and a boolean to mark the end of a word.

2

Create Trie class with insert method

Create a class called Trie with a property root initialized as a new TrieNode(). Add a method insert(word: string): void that inserts the given word into the Trie by creating nodes for each character and marking the last node's isEndOfWord as true.

DSA Typescript

class TrieNode {
    children: Map;
    isEndOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
    }
}

// Your code here

Hint

Loop through each character of the word, add nodes if missing, and mark the last node as end of word.

3

Add search method to Trie

Add a method search(word: string): boolean to the Trie class that returns true if the word exists in the Trie (all characters found and last node's isEndOfWord is true), otherwise returns false.

DSA Typescript

class TrieNode {
    children: Map;
    isEndOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
    }
}

class Trie {
    root: TrieNode;

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

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

// Add search(word: string): boolean method below
// Your code here

Hint

Traverse the Trie for each character. If missing, return false. At end, check if node marks end of word.

4

Insert words and search for a word

Create a Trie instance called trie. Insert the words "apple", "app", and "bat" into trie. Then print the result of trie.search("app").

DSA Typescript

class TrieNode {
    children: Map;
    isEndOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.isEndOfWord = false;
    }
}

class Trie {
    root: TrieNode;

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

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

    search(word: string): boolean {
        let current = this.root;
        for (const char of word) {
            if (!current.children.has(char)) {
                return false;
            }
            current = current.children.get(char)!;
        }
        return current.isEndOfWord;
    }
}

const trie = new Trie();
// Your code here

Hint

Insert each word using insert and then print the result of search("app").