Longest Word in Dictionary Using Trie in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Word Found Using Trie

What is the output of the following Java code that builds a Trie from a list of words and finds the longest word where all prefixes are also words in the dictionary?

DSA Java

import java.util.*;

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isWord = false;
}

class Trie {
    TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
        }
        node.isWord = true;
    }

    public String longestWord() {
        String longest = "";
        Queue<TrieNode> queue = new LinkedList<>();
        Queue<String> words = new LinkedList<>();
        queue.add(root);
        words.add("");

        while (!queue.isEmpty()) {
            TrieNode node = queue.poll();
            String word = words.poll();

            for (int i = 25; i >= 0; i--) {
                TrieNode child = node.children[i];
                if (child != null && child.isWord) {
                    queue.add(child);
                    words.add(word + (char)(i + 'a'));
                    if (word.length() + 1 > longest.length() ||
                        (word.length() + 1 == longest.length() && (word + (char)(i + 'a')).compareTo(longest) < 0)) {
                        longest = word + (char)(i + 'a');
                    }
                }
            }
        }
        return longest;
    }
}

public class Main {
    public static void main(String[] args) {
        String[] words = {"w","wo","wor","worl","world"};
        Trie trie = new Trie();
        for (String w : words) {
            trie.insert(w);
        }
        System.out.println(trie.longestWord());
    }
}

A "wor"

B "worl"

C "world"

D "wo"

💡 Hint

Think about the longest word where every prefix is also a word in the list.

The code inserts all words into a Trie and uses BFS to find the longest word such that all prefixes are present. "world" is the longest word with all prefixes "w", "wo", "wor", "worl" also present.

🧠 Conceptual

intermediate

Understanding Trie Node Structure

Which of the following best describes the purpose of the boolean 'isWord' in a Trie node when finding the longest word in a dictionary?

A It marks the end of a valid word in the dictionary.

B It counts how many words pass through this node.

C It stores the character value of the node.

D It indicates if the node has any children.

💡 Hint

Think about how the Trie knows a word ends.

The 'isWord' boolean marks that the path from root to this node forms a complete word in the dictionary.

🔧 Debug

advanced

Identify the Error in Trie Longest Word Search

What error will occur if the BFS loop in the longestWord method uses 'for (int i = 0; i < 26; i++)' instead of 'for (int i = 25; i >= 0; i--)' when trying to find the lexicographically smallest longest word?

A The method will throw a NullPointerException.

B The method will enter an infinite loop.

C The method will return an empty string.

D The method will return the lexicographically largest longest word instead of the smallest.

💡 Hint

Consider the order in which children are processed in BFS.

Processing children from 25 down to 0 ensures lexicographically smaller words are found last and updated as longest. Reversing the order returns the largest word instead.

📝 Syntax

advanced

Identify Syntax Error in Trie Insert Method

Which option contains a syntax error in the insert method of the Trie class?

DSA Java

public void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        int index = c - 'a'
        if (node.children[index] == null) {
            node.children[index] = new TrieNode();
        }
        node = node.children[index];
    }
    node.isWord = true;
}

A node.isWord = true;

B int index = c - 'a'

C node.children[index] = new TrieNode();

D int index = c - 'a';

💡 Hint

Check for missing semicolons.

Option B is missing a semicolon at the end of the statement, causing a syntax error.

🚀 Application

expert

Longest Word with All Prefixes Present - Result Count

Given the words array {"a", "banana", "app", "appl", "ap", "apply", "apple"}, how many words in this list can be considered the longest word(s) where all prefixes are also present in the dictionary?

A 2

B 0

C 1

D 3

💡 Hint

Check which words have all prefixes present.

Both "apple" and "apply" meet the condition that all their prefixes ("a", "ap", "app", "appl") are present. "banana" does not have prefixes "b", "ba", etc. So two words qualify.

Practice

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

easy

A. To efficiently store and search words by their prefixes

B. To sort words alphabetically

C. To count the total number of words

D. To reverse the words quickly

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 Trie prefix checks.

3. Final Answer:

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

4. Quick Check:

   Trie = prefix search [OK]

Hint: Trie is best for prefix-based word searches [OK]

Common Mistakes:

• Confusing Trie with sorting structures
• Thinking Trie reverses words
• Assuming Trie counts words only

2. Which of the following is the correct way to insert a word into a Trie node in Java?

easy

A. node.children[word[i] - 'a'] = new TrieNode();

B. node.children[word.charAt(i) - 'a'] = new TrieNode();

C. node.children[word.charAt(i)] = new TrieNode();

D. node.children[word.charAt(i) + 'a'] = new TrieNode();

Solution

1. Step 1: Understand character indexing

   Characters are converted to index by subtracting 'a' to map 'a' to 0, 'b' to 1, etc.

2. Step 2: Check Java syntax for charAt

   Java uses word.charAt(i) to get character at index i.

3. Final Answer:

   node.children[word.charAt(i) - 'a'] = new TrieNode(); -> Option B

4. Quick Check:

   Correct char indexing = node.children[word.charAt(i) - 'a'] = new TrieNode(); [OK]

Hint: Use charAt(i) - 'a' for array index in Java [OK]

Common Mistakes:

• Using word[i] instead of charAt(i)
• Adding 'a' instead of subtracting
• Using char directly without index conversion

3. What will be the output of the following Java code snippet that uses a Trie to find the longest word?

String[] words = {"a", "app", "ap", "apply", "apple"};
LongestWordInDictionaryUsingTrie trie = new LongestWordInDictionaryUsingTrie();
System.out.println(trie.longestWord(words));

medium

A. "app"

B. "apply"

C. "apple"

D. "ap"

Solution

1. Step 1: Insert all words into Trie

   Words inserted: "a", "app", "ap", "apply", "apple".

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

   "app" is longest where all prefixes "a", "ap", "app" exist. "apple" and "apply" prefixes "appl" missing.

3. Final Answer:

   "app" -> Option A

4. Quick Check:

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

Hint: Longest word must have all prefixes present [OK]

Common Mistakes:

• Choosing longest word ignoring prefix condition
• Confusing "apple" and "apply" as valid
• Ignoring shorter prefix words

4. Identify the error in this Java method snippet for searching the longest word in a Trie:

public String longestWord(String[] words) {
  TrieNode root = new TrieNode();
  for (String w : words) insert(root, w);
  String result = "";
  dfs(root, new StringBuilder(), result);
  return result;
}

private void dfs(TrieNode node, StringBuilder path, String result) {
  if (node == null) return;
  if (!node.isWord && path.length() != 0) return;
  if (path.length() > result.length()) result = path.toString();
  for (int i = 0; i < 26; i++) {
    if (node.children[i] != null) {
      path.append((char)(i + 'a'));
      dfs(node.children[i], path, result);
      path.deleteCharAt(path.length() - 1);
    }
  }
}

medium

A. The insert method is missing

B. The dfs method does not check for null children

C. The result string is not updated correctly inside dfs due to pass-by-value

D. The path StringBuilder is not cleared after recursion

Solution

1. Step 1: Analyze result parameter usage

   String is immutable and passed by value, so updating result inside dfs does not affect outer variable.

2. Step 2: Understand effect on final output

   Result remains empty because changes inside dfs do not persist outside recursion.

3. Final Answer:

   The result string is not updated correctly inside dfs due to pass-by-value -> Option C

4. Quick Check:

   String immutability causes result update failure [OK]

Hint: Use a mutable object or class field for result [OK]

Common Mistakes:

• Assuming String updates persist in recursion
• Ignoring missing insert method
• Overlooking null checks in children

5. Given a list of words, how would you modify the Trie-based algorithm to return the lexicographically smallest longest word when multiple longest words exist?

hard

A. Store all words in a list and pick the smallest after Trie traversal

B. Sort the input words first and insert into Trie in reverse order

C. Use a max heap to store all longest words and pop the smallest lexicographically

D. Traverse children in alphabetical order during DFS and update result only if new word is longer or lex smaller

Solution

1. Step 1: Traverse children in alphabetical order

   DFS visits children from 'a' to 'z' ensuring lex order traversal.

2. Step 2: Update result conditionally

   Update result only if new word is longer or same length but lex smaller.

3. Step 3: Ensure final result is lex smallest longest word

   This approach naturally picks lex smallest among longest words.

4. Final Answer:

   Traverse children in alphabetical order during DFS and update result only if new word is longer or lex smaller -> Option D

5. Quick Check:

   Lex order DFS + conditional update = Traverse children in alphabetical order during DFS and update result only if new word is longer or lex smaller [OK]

Hint: DFS children from 'a' to 'z' and update result carefully [OK]

Common Mistakes:

• Sorting input but not controlling DFS order
• Using data structures that add unnecessary complexity
• Ignoring lex order during traversal