Longest Word in Dictionary

Longest Word in Dictionary medium

Description

Given a list of words, return the longest word that can be built one character at a time by other words in the list — i.e. every prefix of it (of length 1, 2, …) must also be in the list. If there are ties, return the lexicographically smallest.

Examples

> words = ["w","wo","wor","worl","world"]
  Output: "world"          # w -> wo -> wor -> worl -> world, each a word
 
> words = ["a","banana","app","appl","ap","apply","apple"]
  Output: "apple"          # apple is buildable (a,ap,app,appl,apple); "apply" too,
                           # but "apple" < "apply" lexicographically

Constraints

1 <= words.length <= 1000, total characters ≤ 10^6, lowercase.

Intuition

Insert all words into a trie. A word qualifies iff every node along its path is marked end-of-word — that’s precisely “every prefix is also a word.” DFS the trie, only descending into children that are themselves end-of-word, and track the deepest (then lexicographically smallest) word reachable. Visiting children in alphabetical order makes the lexicographic tie-break automatic.

Try it yourself

Build the trie and DFS only buildable paths, breaking ties lexicographically. The runtime loads once on your first run, then it’s instant.

⌨ Longest Word in Dictionary — return the word

def longestWord(words):
  # longest word buildable one char at a time from other words; ties -> smallest
  # your code here
  pass

Hint

Insert every word into a trie. DFS only into children that are themselves end-of-word (so every prefix is a word). Visit children a-to-z and replace best only on a strictly longer path, so ties favor the smallest word.

Reveal solution

Code

The lexicographic tie-break is free if you DFS in alphabetical order. Iterating children a → z means the first word of a given maximum length you record is automatically the smallest. Only replace best when you find a strictly longer word (>, not >=), so an equal-length-but-later word never overwrites the earlier (smaller) one.

Analysis

Time: O(total characters) to build the trie + O(total characters) to DFS — each node visited once.
Space: O(total characters) for the trie, O(max word length) recursion.

Same skin

Replace Words — both hinge on end-of-word nodes along a path.
Concatenated Words / Word Break — “is this buildable from dictionary pieces?” generalizes this idea.
Implement Trie — the base structure plus a constrained DFS.

Map Sum Pairs Search Suggestions System

Finished this page?