Longest Word in Dictionary Using Trie in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. Each node represents a character, and paths from root to nodes represent prefixes of words.

intermediate

How does a Trie help in finding the longest word in a dictionary where all prefixes are also words?

A Trie allows efficient prefix checking by storing all words. We can traverse the Trie only through nodes that mark the end of a word, ensuring all prefixes exist, and track the longest such word.

beginner

In the context of the longest word problem, what does it mean if a Trie node's 'endOfWord' flag is true?

It means the path from the root to this node forms a valid word in the dictionary, which is important to ensure all prefixes exist when searching for the longest word.

intermediate

Why do we prefer Depth-First Search (DFS) on Trie nodes with 'endOfWord' true when finding the longest word?

DFS helps explore all possible words formed by valid prefixes. By only moving through nodes marking word ends, we ensure prefixes exist and can find the longest valid word.

advanced

What is the time complexity of inserting all words into a Trie and then finding the longest word with all prefixes present?

Inserting all words takes O(N * L) where N is number of words and L is average length. DFS traversal to find longest word also takes O(N * L) in worst case.

What does each node in a Trie typically represent?

A A character of a word

B A whole word

C A number

D A sentence

Each node in a Trie represents a single character of a word.

When searching for the longest word with all prefixes present, which nodes should we only traverse?

A Nodes with endOfWord true

B Nodes with no children

C Nodes with only one child

D All nodes

We only traverse nodes where endOfWord is true to ensure all prefixes are valid words.

What traversal method is commonly used to find the longest word in a Trie?

A Breadth-First Search (BFS)

B Depth-First Search (DFS)

C Level Order Traversal

D Inorder Traversal

DFS is used to explore all valid paths deeply to find the longest word.

What is the main advantage of using a Trie for prefix-related problems?

A Sorting words alphabetically

B Reducing memory usage

C Efficient prefix checking

D Faster integer calculations

Trie allows quick and efficient checking of prefixes.

If a word is 'apple', which nodes must have endOfWord true to consider it valid for the longest word problem?

A 'a' and 'apple' only

B 'apple' only

C 'appl' and 'apple' only

D 'a', 'ap', 'app', 'appl', 'apple'

All prefixes including 'a', 'ap', 'app', 'appl', and 'apple' must be valid words.

Explain how a Trie can be used to find the longest word in a dictionary where every prefix of the word is also a valid word.

Think about how prefixes relate to paths in the Trie.

Describe the steps to insert words into a Trie and then find the longest word with all prefixes present.

Focus on insertion and traversal rules.

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