In a party word game, a player gets a pile of word cards and must lay all of them in one line so that every word starts with the letter the previous word ended with: tiger, rabbit, tapir, raven...
Implement chain_words(words: list[str]) -> list[str]: return the cards in an order that works, or [] if no order uses every card.
- Words are non-empty; they start and end with a lowercase letter. The same word can appear several times; each copy is its own card and must be used.
- A one-letter word such as
"a"starts and ends with the same letter. - If several orders work, return any of them.
- Return
[]for an empty pile.
chain_words(["tapir", "rabbit", "tiger", "raven"])
# ["tiger", "rabbit", "tapir", "raven"] (or ["tapir", "rabbit", "tiger", "raven"], ...)
chain_words(["ab", "ba", "cd"]) # [] "cd" can't join the others
chain_words(["ax", "ay"]) # [] nothing ends in "a" to link them
chain_words(["egg", "gate", "ear"]) # ["egg", "gate", "ear"]
Up to 100,000 words, each at most 10 letters. Aim for O(total length). Trying a card, then backing out when you get stuck, can take exponential time, and a chain this long is far too deep for recursion in Python.
Show hint
Think of each letter as a place and each card as a one-way trip from its first letter to its last. First work out where the line must start from how many trips leave and arrive at each letter. Then walk greedily, and when you get stuck, don't give up: the card you arrived on belongs at the end of the part still to be built.