Coding Interview PatternsLongest Word in Dictionary
MediumTrie

Longest Word in Dictionary

Explanation & Solution

Practice Problem

Description

Given an array of strings words representing an English dictionary, return the longest word in words that can be built one character at a time by other words in words.

If there is more than one possible answer, return the one that is lexicographically smallest. If there is no answer, return the empty string "".

Note that the word should be built from left to right, with each new word adding one letter to the previous word.

Input:words = ["w","wo","wor","worl","world"]
0
w
1
wo
2
wor
3
worl
4
world

Output: "world"

Explanation: The word "world" can be built one character at a time: "w" -> "wo" -> "wor" -> "worl" -> "world". Each intermediate word exists in the dictionary.

Constraints

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 30
  • words[i] consists of lowercase English letters

Approach

Trie pattern

1. Build a Trie from All Words

  • Create a trie root node with children and isEnd properties
  • Insert every word from the array into the trie
  • Mark the terminal node of each word with isEnd = true

2. DFS Traversal of the Trie

  • Perform a depth-first search starting from the root
  • At each node, iterate through children in sorted order (to handle lexicographic tiebreaking)
  • Only continue down a branch if the child node has isEnd = true — this ensures every prefix of the path is a valid word in the dictionary

3. Track the Longest Valid Word

  • Build the current word by appending characters along the path
  • If the current word is longer than the stored result, update the result
  • Because we traverse children in sorted order, the first longest word found is automatically the lexicographically smallest

4. Return the Result

  • After the DFS completes, return the longest word found
  • If no valid word exists (no single-character words in the dictionary), return ""

Key Insight

  • By requiring isEnd = true at every node along the DFS path, we enforce the constraint that the word must be buildable one character at a time from existing dictionary words
  • Sorting children alphabetically during DFS guarantees lexicographic ordering without extra comparison
Time
O(n * m) where n is the number of words and m is the average word length (for trie construction and DFS)
Space
O(n * m) for the trie

Solution Code

Previous
Replace Words
Next
Map Sum Pairs