easy

Longest Word in Dictionary

Find the longest word that can be built one letter at a time, where every step along the way is also a word in the list.

1. Define the problem

Longest Word in Dictionary

Given a list of words, return the longest word that can be built one letter at a time, where every shorter step along the way is also a word in the list. If several words tie for longest, return the smallest one in dictionary order . If no word can be built this way, return the empty string "". Store every word in a trie, then walk down from the root but only ever step onto a node that is itself the end of a word. Any path you can walk under that rule is a word that was buildable letter by letter. Visiting the child letters in alphabetical order and only replacing the answer when the new path is strictly longer gives the dictionary-order tie-break for free.

Constraints

  • 1 ≤ words.length ≤ 1000
  • 1 ≤ wordsi.length ≤ 30
  • wordsi consists of lowercase English letters only

Example

Inputwords = ["w", "wo", "wor", "worl", "world"]
Output"world"

Explanation Each step of "world" is itself in the list: "w", then "wo", then "wor", then "worl", then "world". So the whole word can be built one letter at a time.

2. Know the words first

In plain terms

Dictionary order
The order words appear in a dictionary: compare letter by letter, and the first difference decides. "apple" comes before "apply" because e comes before y.
Depth-first walk
Exploring one path all the way down before backing up and trying the next branch.
Buildable word
A word where every prefix of it, from one letter up to the whole thing, is also in the list. "world" is buildable if "w", "wo", "wor" and "worl" are all present.
3. Visualize the solution

Walking down the trie, stepping only onto complete words

Walking down the trie, stepping only onto complete words
Statusinit

All five words go into the trie; the walk starts at the root with best = "".

What happens in this step

words = ["w", "wo", "wor", "worl", "world"]
best = ''
walk(root, '')

The root counts as an end of word so the walk is allowed to start from it.
Step 1 of 7

Steps to visualize

  1. The row of cells is the path being walked, one cell per letter of the candidate word.
  2. A cell value of "word" means a word in the list ends at that node, so the walk is allowed to step onto it.
  3. The frame covers the path built so far, which is the current candidate answer.
  4. The best answer is replaced only when a path is strictly longer than the one already found.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walking down the trie, stepping only onto complete words
Statusinit

All five words go into the trie; the walk starts at the root with best = "".

What happens in this step

words = ["w", "wo", "wor", "worl", "world"]
best = ''
walk(root, '')

The root counts as an end of word so the walk is allowed to start from it.
Step 1 of 7
5. Solution

Solution

solution.tsTypeScript
function longestWord(words) {
  class TrieNode {
    constructor() {
      this.children = {};
      this.isEnd = false;
    }
  }

  const root = new TrieNode();
  root.isEnd = true;

  for (const word of words) {
    let node = root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  let best = '';

  const walk = (node, built) => {
    if (built.length > best.length) {
      best = built;
    }

    const letters = Object.keys(node.children).sort();

    for (const ch of letters) {
      const child = node.children[ch];
      if (child.isEnd) {
        walk(child, built + ch);
      }
    }
  };

  walk(root, '');

  return best;
}
Time
O(total letters across all words)
Space
O(total letters across all words)
6. Test cases

Test cases

InputExpectedCovers
words = ["w", "wo", "wor", "worl", "world"]"world"example from the docstring
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]"apple"two words tie at length 5, so the dictionary-smaller one wins
words = ["abc"]""the chain is broken from the first letter, so nothing can be built
words = ["b", "a"]"a"all words are one letter, so the alphabetically smallest wins
words = ["ab", "a"]"ab"the input order of the list has no effect on the answer
words = ["a", "ab", "abc", "z", "zz"]"abc"two buildable branches of different lengths, the longer one wins

Keep reading