Longest Word in Dictionary Using Trie in DSA C++ - 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 "a", "ap", "app", "appl", and "apple" are in the list, "apple" is the longest word that can be built step by step.

🎯 Goal: You will build a program using a Trie data structure to find the longest word in a list where every prefix of the word is also in the list.

📋 What You'll Learn

Create a TrieNode class with children and end-of-word marker

Insert all words from the given list into the Trie

Use a helper variable to track the longest word found

Traverse the Trie to find the longest word where all prefixes exist

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 string search algorithms is important for software engineering roles involving text processing, search engines, and data indexing.

1

Create TrieNode class and insert words

Create a class called TrieNode with a public array children of size 26 initialized to nullptr and a boolean isEnd initialized to false. Then create a class called Trie with a public root node of type TrieNode*. Add a public method insert that takes a string word and inserts it into the Trie. Finally, create a vector of strings called words with these exact values: "w", "wo", "wor", "worl", "world" and insert each word into the Trie using the insert method.

DSA C++

# Your code here

Hint

Remember to initialize all children pointers to nullptr and set isEnd to false in the TrieNode constructor. Insert each word character by character.

2

Add helper variable to track longest word

Add a global string variable called longestWord initialized to an empty string "" to keep track of the longest valid word found so far.

DSA C++

#include 
#include 
#include 
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        for (int i = 0; i children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
};

vector words = {"w", "wo", "wor", "worl", "world"};
Trie trie;

string longestWord = "";  // Your code here

int main() {
    for (string word : words) {
        trie.insert(word);
    }
    // Your code here
    return 0;
}

Hint

Declare longestWord outside main() so it can be used in other functions later.

3

Traverse Trie to find longest valid word

Add a recursive function called dfs that takes a TrieNode* called node and a string currentWord. The function should check if node->isEnd is true or if node is the root. If not, return immediately. If currentWord is longer than longestWord or equal length but lexicographically smaller, update longestWord. Then for each child from 'a' to 'z', if the child exists, call dfs recursively with the child node and currentWord plus the child's character. Call dfs from main starting with trie.root and empty string "".

DSA C++

#include 
#include 
#include 
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        for (int i = 0; i children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
};

vector words = {"w", "wo", "wor", "worl", "world"};
Trie trie;

string longestWord = "";

void dfs(TrieNode* node, string currentWord) {
    // Your code here
}

int main() {
    for (string word : words) {
        trie.insert(word);
    }
    dfs(trie.root, "");
    return 0;
}

Hint

Check if the current node is the root or marks the end of a word before continuing. Update longestWord if the current word is longer or lexicographically smaller when lengths are equal.

4

Print the longest word found

Add a cout statement in main to print the value of longestWord.

DSA C++

#include 
#include 
#include 
using namespace std;

class TrieNode {
public:
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        for (int i = 0; i children[index]) {
                node->children[index] = new TrieNode();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
};

vector words = {"w", "wo", "wor", "worl", "world"};
Trie trie;

string longestWord = "";

void dfs(TrieNode* node, string currentWord) {
    if (node != trie.root && !node->isEnd) {
        return;
    }
    if (currentWord.length() > longestWord.length() ||
        (currentWord.length() == longestWord.length() && currentWord children[i]) {
            dfs(node->children[i], currentWord + char('a' + i));
        }
    }
}

int main() {
    for (string word : words) {
        trie.insert(word);
    }
    dfs(trie.root, "");
    cout << longestWord << endl;  // Your code here
    return 0;
}

Hint

Use cout << longestWord << endl; to print the longest word after the DFS completes.

Practice

1. What is the main purpose of using a Trie data structure when finding the longest word in a dictionary?

easy

A. To sort words alphabetically

B. To reverse the words in the dictionary

C. To count the total number of words

D. To efficiently store and search words by their prefixes

Solution

1. Step 1: Understand Trie usage

   A Trie stores words by their prefixes, allowing quick prefix checks.

2. Step 2: Relate to longest word search

   Finding the longest word with all prefixes present is easier with prefix-based storage.

3. Final Answer:

   To efficiently store and search words by their prefixes -> Option D

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie stores prefixes for fast word checks [OK]

Common Mistakes:

• Thinking Trie sorts words alphabetically
• Confusing Trie with simple arrays
• Assuming Trie counts words only

2. Which of the following is the correct way to declare a Trie node class in C++ for lowercase English letters?

easy

A. class TrieNode { public: vector<TrieNode> children; bool isEnd; TrieNode() { isEnd = false; } };

B. class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } };

C. class TrieNode { public: TrieNode* children[52]; bool isEnd; TrieNode() { for(int i=0; i<52; i++) children[i] = nullptr; isEnd = false; } };

D. class TrieNode { public: int children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = 0; isEnd = true; } };

Solution

1. Step 1: Check children type and size

   Children should be pointers to TrieNode, size 26 for lowercase letters.

2. Step 2: Check initialization

   Initialize all children to nullptr and isEnd to false.

3. Final Answer:

   class TrieNode { public: TrieNode* children[26]; bool isEnd; TrieNode() { for(int i=0; i<26; i++) children[i] = nullptr; isEnd = false; } }; -> Option B

4. Quick Check:

   Pointer array size 26, initialized null [OK]

Hint: Use pointer array size 26 for lowercase letters [OK]

Common Mistakes:

• Using int array instead of pointers
• Wrong array size (52 instead of 26)
• Not initializing children to nullptr

3. What will be the output of the following code snippet that inserts words into a Trie and finds the longest word where all prefixes exist? vector<string> words = {"a", "ap", "app", "appl", "apple", "apply"}; // After building Trie and searching longest word cout << longestWord(words) << endl;

medium

A. "apple"

B. "apply"

C. "appl"

D. "app"

Solution

1. Step 1: Insert all words into Trie

   Words "a", "ap", "app", "appl", "apple", "apply" are inserted.

2. Step 2: Find longest word with all prefixes present

   "apple" and "apply" both have all prefixes present, but "apple" comes first lexicographically.

3. Final Answer:

   "apple" -> Option A

4. Quick Check:

   Longest word with all prefixes = "apple" [OK]

Hint: Check all prefixes exist; choose longest lex smallest [OK]

Common Mistakes:

• Choosing "apply" ignoring lex order
• Choosing shorter words like "app"
• Not verifying all prefixes exist

4. Identify the error in this Trie insertion code snippet for lowercase English letters: void insert(TrieNode* root, string word) { TrieNode* node = root; for (char c : word) { int index = c - 'a'; if (!node->children[index]) node->children[index] = new TrieNode(); node = node->children[index]; } node->isEnd = true; }

medium

A. No error; code is correct

B. Incorrect calculation of index from character

C. Missing initialization of root node before insertion

D. Not marking the end of word after insertion

Solution

1. Step 1: Check index calculation

   Index is correctly calculated as c - 'a' for lowercase letters.

2. Step 2: Verify insertion and end marking

   Children nodes are created if null, and isEnd is set true after insertion.

3. Final Answer:

   No error; code is correct -> Option A

4. Quick Check:

   Insertion logic correct [OK]

Hint: Check index and isEnd marking carefully [OK]

Common Mistakes:

• Miscomputing index for uppercase letters
• Forgetting to mark isEnd true
• Not initializing root before use (outside snippet)

5. Given a list of words, how would you modify the Trie-based approach to find the longest word where every prefix is also a valid word, but now the dictionary may contain uppercase and lowercase letters mixed? Choose the best approach.

hard

A. Ignore case and treat uppercase and lowercase as same during insertion

B. Convert all words to lowercase before inserting into Trie and searching

C. Use a Trie with 52 children per node to handle both cases distinctly

D. Use a hash map instead of Trie for faster prefix checks

Solution

1. Step 1: Understand case sensitivity

   Uppercase and lowercase letters differ; need to distinguish them in Trie.

2. Step 2: Adjust Trie structure

   Use 52 children per node (26 lowercase + 26 uppercase) to store all letters distinctly.

3. Final Answer:

   Use a Trie with 52 children per node to handle both cases distinctly -> Option C

4. Quick Check:

   Handle case by expanding Trie size [OK]

Hint: Expand Trie children to 52 for mixed case [OK]

Common Mistakes:

• Converting all to lowercase loses case info
• Ignoring case causes wrong matches
• Using hash map loses prefix tree benefits