Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtrie

Longest Word in Dictionary

Problem (restated)

From a list of words, return the longest word that can be built one letter at a time from other words in the list. Ties → lexicographically smallest. Empty if none.

Intuition

A valid word has every proper prefix also in the dictionary. Sort by length desc then lex, pick first valid.

Approaches

Prefix-chain via set (trie idea)

Unverified

Time O(Σ L^2)Space O(Σ L)

Idea. Hash set of words; check all prefixes. Trie DFS from root preferring end-marked children is equivalent.

Walkthrough. [“w”,“wo”,“wor”,“worl”,“world”] → “world”.

Trade-offs. Set of prefixes is enough; full trie shines when inserting incrementally.

Solution

export function longestWord(words: string[]): string {
  const set = new Set(words);
  words = [...words].sort((a, b) => b.length - a.length || (a < b ? -1 : a > b ? 1 : 0));
  for (const w of words) {
    let ok = true;
    for (let i = 1; i < w.length; i++) {
      if (!set.has(w.slice(0, i))) {
        ok = false;
        break;
      }
    }
    if (ok) return w;
  }
  return "";
}

export function longestWord(words: string[]): string {
  const set = new Set(words);
  words = [...words].sort((a, b) => b.length - a.length || (a < b ? -1 : a > b ? 1 : 0));
  for (const w of words) {
    let ok = true;
    for (let i = 1; i < w.length; i++) {
      if (!set.has(w.slice(0, i))) {
        ok = false;
        break;
      }
    }
    if (ok) return w;
  }
  return "";
}

Template connection

Trie / prefix chain completeness.

Reflection

Every prefix of a candidate must also be in the dictionary. Keep the longest word. On a tie, keep the lexicographically smaller one.
A set of prefix checks asks the same question as a trie. A long word with a missing prefix is out.
A single letter is always a candidate. An empty dictionary answers the empty string.