Longest Word in Dictionary Using Trie in DSA Typescript - Build from Scratch

Longest Word in Dictionary Using Trie

📖 Scenario: You are building a word game helper tool. You have a list of words and want to find the longest word that can be built one character at a time by other words in the list.For example, if the list contains "a", "ap", "app", "appl", "apple", and "apply", the longest word that can be built step-by-step is "apple" or "apply".

🎯 Goal: Build a Trie data structure to store the words. Then find the longest word in the dictionary where every prefix is also a word in the dictionary.

📋 What You'll Learn

Create a TrieNode class with children and endOfWord properties

Create a Trie class with insert and longestWord methods

Insert all words from the given list into the Trie

Find the longest word where all prefixes exist in the Trie

Print the longest valid word found

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and word games to quickly find words and prefixes.

💼 Career

Understanding Tries and prefix-based searches is useful for software engineering roles involving search engines, text processing, and data indexing.

1

Create the TrieNode class

Create a class called TrieNode with a property children as a Map from string to TrieNode and a boolean property endOfWord initialized to false.

DSA Typescript

# Your code here

Hint

Think of TrieNode as a box that can hold links to other boxes (children) and a flag to say if a word ends here.

2

Create the Trie class and 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 endOfWord as true.

DSA Typescript

class TrieNode {
    children: Map;
    endOfWord: boolean;

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

// Create the Trie class with root and insert method
# Your code here

Hint

Insert each character by moving down the Trie, creating new nodes if needed, and mark the end of the word.

3

Add longestWord method to find the longest valid word

Add a method longestWord(words: string[]): string to the Trie class. Insert all words into the Trie. Then find the longest word where every prefix is marked endOfWord in the Trie. Return the longest such word. If multiple words have the same length, return the lexicographically smallest.

DSA Typescript

class TrieNode {
    children: Map;
    endOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.endOfWord = 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.endOfWord = true;
    }

    // Add longestWord method below
    # Your code here
}

Hint

Use depth-first search starting from root. Only continue down nodes where endOfWord is true. Keep track of the longest valid word found.

4

Print the longest word found from the given list

Create a variable words with the exact list ["a", "ap", "app", "appl", "apple", "apply"]. Create a Trie instance called trie. Call trie.longestWord(words) and print the result using console.log.

DSA Typescript

class TrieNode {
    children: Map;
    endOfWord: boolean;

    constructor() {
        this.children = new Map();
        this.endOfWord = 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.endOfWord = true;
    }

    longestWord(words: string[]): string {
        for (const word of words) {
            this.insert(word);
        }

        let longest = "";

        const dfs = (node: TrieNode, path: string): void => {
            if (path.length > longest.length || (path.length === longest.length && path  a[0].localeCompare(b[0]))) {
                if (child.endOfWord) {
                    dfs(child, path + char);
                }
            }
        };

        dfs(this.root, "");
        return longest;
    }
}

// Create words array, Trie instance, and print longest word
# Your code here

Hint

Use the longestWord method on the trie instance with the given words array and print the result.