Longest Word in Dictionary — Trie BFS for Buildable Words

Problem Statement#

LeetCode 720 — Longest Word in Dictionary | Difficulty: Medium

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 longest word with the smallest lexicographical order. If there is no answer, return the empty string.

A word is buildable if every prefix of the word — word[0:1], word[0:2], ..., word[0:len-1] — is also in words.

Constraints:

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

Examples:

Input: words = ["w","wo","wor","worl","world"]
Output: "world"
Explanation: "world" can be built from "w" → "wo" → "wor" → "worl" → "world".

Input: words = ["a","banana","app","appl","ap","apply","apple"]
Output: "apple"
Explanation: Both "apply" and "apple" are buildable; "apple" is lex smaller.

Why This Problem Matters#

This problem looks innocent but it tests two skills at once: prefix containment (a textbook trie use case) and lexicographic tie-breaking. Asked at Amazon, Google, and Bloomberg, it is a perfect medium because the trie naturally encodes "is every prefix a word?" via the chain of isEnd flags along the path.

The naive O(N times L) hash-set approach works, but the trie + BFS solution is more elegant: every node we visit is provably buildable, and exploring children in alphabetical order guarantees lex-smallest results without an extra sort.

The Core Insight#

A word is buildable if and only if every node along its path in the trie has isEnd = True. So the algorithm is:

1. Build a trie of all words with isEnd flags.
2. BFS from the root, only descending into children whose isEnd = True.
3. Track the deepest node reached. On ties, prefer alphabetically earlier words.

BFS guarantees we explore nodes by depth, so the first time we reach max depth we have a longest answer. By iterating children in alphabetical order (a → z), the BFS naturally produces the lex-smallest among equally deep paths if we update only on strictly deeper finds.

Equivalently, you can do DFS in reverse-alphabetical order so that lex-smaller branches are explored last (and overwrite previous best).

Visual Dry Run#

Words: ["a","app","apple","appl","ap","apply"]. Trie with isEnd markers (*):

root
 └── a*
      └── p*
           └── p*
                ├── l*  (appl)
                │    ├── e*  (apple)
                │    └── y*  (apply)
                └── (no e at depth 4)

BFS from root, descending only through isEnd nodes:

queue: [a*]                        → ans = "a"
expand a*: child p*                → queue: [ap]
expand ap*: child p*               → queue: [app]
expand app*: children l*, (others) → queue: [appl]
expand appl*: children e*, y*      → queue: [apple, apply]
expand apple*: no isEnd children   → ans = "apple" (depth 5)
expand apply*: no isEnd children   → tied depth, but "apple" < "apply"

Final answer: "apple". The lex tie-break came naturally because we expanded children in alphabetical order and only update ans when the new length is strictly greater.

Solution (Optimal) — Trie + BFS#

Python#

from collections import deque
 
class TrieNode:
    __slots__ = ("children", "is_end", "word")
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.word = ""    # cache full word at terminal node
 
class Solution:
    def longestWord(self, words: list[str]) -> str:
        root = TrieNode()
        for w in words:
            node = root
            for ch in w:
                node = node.children.setdefault(ch, TrieNode())
            node.is_end = True
            node.word = w
 
        # BFS through buildable nodes only
        ans = ""
        q = deque([root])
        while q:
            node = q.popleft()
            # Iterate children in alphabetical order so equal-length wins go to lex-smallest
            for ch in sorted(node.children):
                child = node.children[ch]
                if child.is_end:
                    if len(child.word) > len(ans) or (
                        len(child.word) == len(ans) and child.word < ans
                    ):
                        ans = child.word
                    q.append(child)
        return ans

JavaScript#

var longestWord = function (words) {
  const root = {};
  for (const w of words) {
    let node = root;
    for (const ch of w) {
      if (!node[ch]) node[ch] = {};
      node = node[ch];
    }
    node.isEnd = true;
    node.word = w;
  }
 
  let ans = "";
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    const keys = Object.keys(node).filter((k) => k.length === 1).sort();
    for (const ch of keys) {
      const child = node[ch];
      if (child.isEnd) {
        if (child.word.length > ans.length ||
           (child.word.length === ans.length && child.word < ans)) {
          ans = child.word;
        }
        queue.push(child);
      }
    }
  }
  return ans;
};

Alternative — Sort + HashSet#

class Solution2:
    def longestWord(self, words: list[str]) -> str:
        words.sort(key=lambda w: (-len(w), w))   # longest first, lex tie-break
        word_set = set(words)
        for w in words:
            if all(w[:i] in word_set for i in range(1, len(w))):
                return w
        return ""

Complexity#

• Trie build: O(sum of word lengths).
• BFS: O(sum of word lengths) — each node visited once.
• Space: O(sum of word lengths) for the trie.

Common Mistakes#

1. Forgetting to mark every prefix in the trie — only word terminals get isEnd = True. The buildability check requires that every prefix node also be isEnd, which works only because each prefix is itself in the dictionary.
2. Returning an unbuildable word — DFS without checking isEnd at every level lets you reach leaves that are not buildable.
3. Wrong tie-break direction — < vs >. The smaller string lexicographically wins on ties.
4. Not caching the full word at the terminal — reconstructing the word from the path adds O(L) per terminal; caching is O(1).
5. Iterating children in unsorted order — works if you compare both length and lex, but breaks if you only compare length.
6. DFS without explicit ordering — DFS in alphabetical order works too, but you must update ans only on strictly deeper, never on equal lex.

Interview Tips#

• State the buildability condition explicitly: "every prefix must be in the dictionary."
• Justify the trie: it natively tests every prefix in O(1) at each step.
• Mention the BFS-by-depth argument for guaranteeing longest-first exploration.
• Discuss tie-breaking: alphabetical iteration plus strict length comparison gives lex-smallest for free.
• For the sort + hashset alternative, mention that the sort key encodes both length (descending) and lex (ascending), and you can early-return on the first match.

Follow-up Questions#

• What if some words have zero-length prefixes (empty string)? Treat root as isEnd = True if appropriate; otherwise the first character must be in the dictionary.
• Multiple longest words required? Modify to collect all words tied at the max depth.
• Streaming dictionary? Insert into the trie as words arrive; recompute ans after each insert by re-running BFS or maintaining the running best.
• Reverse problem — longest word that builds others? A different problem; would require subtree-size aggregation.
• What if word lengths are huge? The trie scales linearly in total characters; constraint here caps it at 30k.

Key Takeaways#

• Trie + BFS finds the longest buildable word in linear time.
• Buildability means every prefix node has isEnd = True — encoded perfectly by a trie.
• Iterate children alphabetically and update only on strictly greater length to get lex-smallest for free.
• Cache the full word at terminal nodes to avoid path reconstruction.
• The sort + hashset alternative is concise and pragmatic for small inputs.
• This pattern generalises to "longest path under a constraint" problems on prefix structures.