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

Longest Word in Dictionary Using Trie

📖 Scenario: Imagine you have a list of words from a dictionary. You 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 word is "apple", then "a", "ap", "app", "appl" must also be in the list.

🎯 Goal: You will build a Trie data structure to store the words. Then, you will write code to find the longest word that can be built character by character from other words in the dictionary.

📋 What You'll Learn

Create a TrieNode class with children and endOfWord properties

Create a Trie class with insert and search methods

Insert all words from the given list into the Trie

Find the longest word that can be built one character at a time using the Trie

Print the longest 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 searches is useful for software engineers working on search engines, text processing, and data compression.

1

Create TrieNode and Trie classes

Create a class called TrieNode with a constructor that initializes children as an empty object and endOfWord as false. Then create a class called Trie with a constructor that initializes root as a new TrieNode.

DSA Javascript

// Create TrieNode class
// Create Trie class with root property
// Your code here

Hint

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

2

Add insert method to Trie

Add an insert method to the Trie class that takes a word string. Use a variable node starting at this.root. For each character in word, if the character is not in node.children, create a new TrieNode for it. Move node to the child node. After the loop, set node.endOfWord to true.

DSA Javascript

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

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

    // Add insert method here
    // Your code here
}

Hint

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

3

Insert words and find longest buildable word

Create a variable words with the array ["a", "ap", "app", "appl", "apple", "apply"]. Create a Trie instance called trie. Insert each word from words into trie using the insert method. Then create a function longestWord that takes words and trie. It should find the longest word where every prefix is also a word in the trie. Use a helper function to check prefixes. Return the longest such word.

DSA Javascript

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

// Create words array and insert words into trie
// Create longestWord function
// Your code here

Hint

Check each word's prefixes by walking the trie. Keep track of the longest valid word.

4

Print the longest word

Call the longestWord function with words and trie. Print the returned longest word using console.log.

DSA Javascript

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

const words = ["a", "ap", "app", "appl", "apple", "apply"];
const trie = new Trie();
for (const word of words) {
    trie.insert(word);
}

function longestWord(words, trie) {
    let longest = "";

    function canBuild(word) {
        let node = trie.root;
        for (const char of word) {
            node = node.children[char];
            if (!node || !node.endOfWord) {
                return false;
            }
        }
        return true;
    }

    for (const word of words) {
        if (canBuild(word)) {
            if (word.length > longest.length || (word.length === longest.length && word < longest)) {
                longest = word;
            }
        }
    }
    return longest;
}

// Print the longest word
// Your code here

Hint

Use console.log(longestWord(words, trie)) to print the result.