Longest Word Built Letter by Letter
Problem
A word game lets a player grow a word one letter at a time, adding each letter to the end, and every intermediate step must itself be a word from the dictionary. Given the dictionary, return the longest word that can be built this way starting from a one-letter word. If several words tie on length, return the alphabetically smallest; if none can be built, return an empty string.
Examples
Input: words = ["w", "wo", "wor", "worl", "world"]
Output: "world"Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Why: "apply" is also buildable and just as long, but "apple" sorts firstInput: words = ["cat", "ca"]
Output: ""
Why: edge case, "c" is missing, so no chain can startHints
0 / 3
A word is buildable exactly when every one of its prefixes is in the dictionary. Checking that for each word separately repeats the same prefix checks many times.
Put the words into a prefix tree and mark the nodes where a word ends. A buildable word is then a path from the root on which every node carries that marker.
Walk the tree from the root, but only step into a child that marks the end of a word. Every node you reach this way is a buildable word; keep the longest, breaking ties by the smaller word.
Solution
A word can be built letter by letter exactly when each of its prefixes is also a word, which in a prefix tree means every node along its path carries an end-of-word marker. So the search walks the tree from the root and only descends into children that end a word; branches whose next step is not a word are never entered. Every node reached is a buildable word, and the answer is the longest one, with ties broken alphabetically. Building the tree takes O(total characters), and the walk visits each node at most once, so time and space are both O(total characters).
def longest_buildable(words):
root = {}
for w in words:
node = root
for ch in w:
node = node.setdefault(ch, {})
node["$"] = w # the word that ends here
best, stack = "", [root]
while stack:
node = stack.pop()
for ch, child in node.items():
if ch != "$" and "$" in child: # only step onto real words
w = child["$"]
if len(w) > len(best) or (len(w) == len(best) and w < best):
best = w
stack.append(child)
return best
print(longest_buildable(["w", "wo", "wor", "worl", "world"])) # -> world
print(longest_buildable(["a", "banana", "app", "appl", "ap", "apply", "apple"])) # -> apple
print(longest_buildable(["cat", "ca"]) == "") # -> TrueStuck on the idea rather than the code? Trie Basics covers it.