Longest Word in Dictionary Using Trie in DSA Java

Mental Model

We build a tree where each path from root to a node forms a prefix of words. We find the longest word where every prefix is also a word.

Analogy: Imagine a tree of building blocks where each block adds a letter. We only keep paths where every step is a valid smaller word, like building a tower where each floor is stable.

root
 ↓
 t -> r -> i -> e
 ↑
 (start)

Dry Run Walkthrough

Input: words: ["a", "app", "ap", "apply", "apple", "appl", "b", "ban", "banana"]

Goal: Find the longest word where every prefix is also in the list

Step 1: Insert "a" into trie marking end of word

root -> a* (end)
 ↑

Why: Start building trie with first word

Step 2: Insert "ap" marking end at 'p'

root -> a* -> p* (end)
 ↑

Why: Add prefix 'ap' which is a word

Step 3: Insert "app" marking end at second 'p'

root -> a* -> p* -> p* (end)
 ↑

Why: Add longer prefix 'app' which is a word

Step 4: Insert "appl" marking end at 'l'

root -> a* -> p* -> p* -> l* (end)
 ↑

Why: Add prefix 'appl' which is a word

Step 5: Insert "apple" marking end at 'e'

root -> a* -> p* -> p* -> l* -> e* (end)
 ↑

Why: Add full word 'apple' with all prefixes valid

Step 6: Insert "apply" marking end at 'y'

root -> a* -> p* -> p* -> l* -> y* (end)
 ↑

Why: Add another full word 'apply' with valid prefixes

Step 7: Insert "b" marking end at 'b'

root -> a* -> ...
      ↓
      b* (end)
 ↑

Why: Add separate branch for 'b'

Step 8: Insert "ban" marking end at 'n'

root -> a* -> ...
      ↓
      b* -> a -> n* (end)
 ↑

Why: Add 'ban' word

Step 9: Insert "banana" marking end at last 'a'

root -> a* -> ...
      ↓
      b* -> a -> n* -> a -> n -> a* (end)
 ↑

Why: Add 'banana' word

Step 10: Search trie for longest word where all prefixes are words

Check 'a', 'ap', 'app', 'appl', 'apple', 'apply' and 'b', 'ban', 'banana'

Why: We want the longest word with all prefixes valid

Result:

Longest word: apple
root -> a* -> p* -> p* -> l* -> e* (end)
 ↑

Annotated Code

DSA Java

import java.util.*;

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

public class LongestWordInDictionary {
    private TrieNode root;

    public LongestWordInDictionary() {
        root = new TrieNode();
    }

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

    public String longestWord(String[] words) {
        for (String w : words) {
            insert(w);
        }
        String longest = "";
        Queue<TrieNodeWord> queue = new LinkedList<>();
        queue.offer(new TrieNodeWord(root, ""));

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

            if (word.length() > longest.length() || (word.length() == longest.length() && word.compareTo(longest) < 0)) {
                longest = word;
            }

            for (int i = 0; i < 26; i++) {
                TrieNode child = node.children[i];
                if (child != null && child.isEnd) {
                    queue.offer(new TrieNodeWord(child, word + (char)(i + 'a')));
                }
            }
        }
        return longest;
    }

    private static class TrieNodeWord {
        TrieNode node;
        String word;

        TrieNodeWord(TrieNode node, String word) {
            this.node = node;
            this.word = word;
        }
    }

    public static void main(String[] args) {
        LongestWordInDictionary trie = new LongestWordInDictionary();
        String[] words = {"a", "app", "ap", "apply", "apple", "appl", "b", "ban", "banana"};
        System.out.println(trie.longestWord(words));
    }
}

for (String w : words) { insert(w); }

Insert all words into trie to build structure

queue.offer(new TrieNodeWord(root, ""));

Start BFS from root with empty word

TrieNodeWord curr = queue.poll();

Get next node and word from queue

if (word.length() > longest.length() || (word.length() == longest.length() && word.compareTo(longest) < 0)) { longest = word; }

Update longest word if current is longer or lex smaller if same length

for (int i = 0; i < 26; i++) { if (child != null && child.isEnd) { queue.offer(new TrieNodeWord(child, word + (char)(i + 'a'))); } }

Add children nodes to queue only if they mark end of a word (valid prefix)

Output

apple

Complexity Analysis

Time: O(N * L) because we insert N words each of length L and then BFS visits nodes up to total characters

Space: O(N * L) for trie storage of all words and BFS queue

vs Alternative: Compared to checking prefixes by sorting and scanning, trie allows prefix checks in O(1) per character, making prefix validation efficient

Edge Cases

Empty word list

Returns empty string as no words exist

DSA Java

for (String w : words) { insert(w); }

Words with no valid prefixes except single letters

Returns the longest single-letter word

DSA Java

if (child != null && child.isEnd) { queue.offer(...) }

Multiple longest words with same length

Returns lexicographically smallest among them

DSA Java

if (word.length() == longest.length() && word.compareTo(longest) < 0) { longest = word; }

When to Use This Pattern

When asked to find the longest word where all prefixes are valid words, use a trie to efficiently check prefixes and BFS to find the longest valid path.

Common Mistakes

Mistake: Not checking if prefixes are words before adding children to BFS queue
Fix: Only add child nodes to BFS queue if child.isEnd is true to ensure prefix validity

Mistake: Comparing words incorrectly for lex order when lengths are equal
Fix: Use word.compareTo(longest) < 0 to pick lexicographically smaller word

Summary

Build a trie from words and find the longest word where every prefix is also a word.

Use when you need to find words with all prefixes valid efficiently.

The key insight is to only explore trie paths where each node marks the end of a valid prefix.

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