Longest Word in Dictionary (LeetCode 720)

The problem

You get a list of words. Find the longest word that can be built one character at a time, where every intermediate prefix is also a word in the list. If there is a tie, return the one that comes first alphabetically. If no word qualifies, return "".

Input:  ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"

Both apple and apply can be built as a → ap → app → appl → ..., and both have length 5; apple is smaller alphabetically. banana fails because b is not in the list.

How to think about it

Start with brute force. Put all words in a set. For each word, check every prefix (w[:1], w[:2], …) is in the set. A word of length L needs L slices and lookups of up to L characters each, so O(L²) per word. It works, but checks the same prefixes again for every word that shares them.

The key insight: a word is buildable if the word without its last letter is buildable. That is a recurrence, so process words in an order where the shorter prefix is always seen first. Sorting does that: "ap" sorts before "app", which sorts before "appl". Keep a set built, seeded with "". Walking the sorted list, a word joins built exactly when w[:-1] is already in it. Now each word needs one lookup, not L.

Ties for free. Because the scan is alphabetical, the first word of a given length you accept is the smallest one. Only replacing best on a strictly longer word keeps it.

Which pattern is this? It is the trie idea expressed with a set: a word is valid only if every node on its path is a word end. The trie version inserts all words and runs a DFS that only goes into children marked as word ends. The tell is “built one character at a time”.

Approach

1. Sort the words.
2. Start with built = {""} and best = "".
3. For each word in sorted order, if w[:-1] is in built, add w to built.
4. If that word is strictly longer than best, make it the new best.
5. Return best.

Solution

def longestWord(words):
    words.sort(); built = set(['']); best = ""
    for w in sorted(words):
        if w[:-1] in built:                 # its one-shorter prefix is buildable
            built.add(w)
            if len(w) > len(best): best = w # strictly longer keeps the smallest tie
    return best
# longestWord(["w","wo","wor","worl","world"]) -> "world"

Dry run

On the example, the sorted order is a, ap, app, appl, apple, apply, banana:

The answer is "apple".

Complexity

• Time: O(n log n · L) for sorting n words of length up to L (string comparisons cost O(L)). The scan is O(n·L) because w[:-1] copies the string.
• Space: O(n·L) for the built set. The trie version uses the same order of space.

Edge cases and pitfalls

• No one-letter words means nothing is buildable, and the answer is "" (for example ["abc"]).
• Ties (["b", "a"] gives "a"): use > not >=, or you keep the alphabetically larger word.
• Skipping the sort breaks it: "app" might be seen before "ap" is in the set.
• Sorting mutates the input. words.sort() changes the caller’s list; the second sorted() call is redundant but harmless.

Related problems

• Implement Trie (Prefix Tree) (LeetCode 208): the trie alternative inserts every word, then DFS only through word-end nodes.
• Longest Common Prefix (LeetCode 14): another question about a path where every node satisfies a rule.
• Word Break (LeetCode 139): building a string from dictionary words, solved with DP.