Concatenated words: find words built from other words in the list

Given a list of distinct words, return every word that can be split into two or more pieces, in order, where each piece is a word in the list. The same word may be used as a piece more than once. A word cannot be made from itself alone. Return them in their order in the input.

A shorter variant asks only for words made of exactly two other words from the list.

Interface

Unless you agree on a different interface with the interviewer, assume:

• concatenated_words(words: list[str]) -> list[str]

Example

words = ["cat", "cats", "dog", "catsdog", "dogcatsdog", "rat", "ratcatdogcat", "catdog"]
concatenated_words(words)  ->  ["catsdog", "dogcatsdog", "ratcatdogcat", "catdog"]
    # dogcatsdog = dog + cats + dog; ratcatdogcat = rat + cat + dog + cat
exactly two pieces        ->  ["catsdog", "dogcatsdog", "catdog"]
    # dogcatsdog = dog + catsdog also counts as two pieces

Constraints

• Up to 10^4 words, each 1 to 30 lowercase letters, total length up to 10^5.
• Words are distinct. The empty string, if present, is not a valid piece.

Clarifying questions

• Can a piece be reused within one word?
• Does the empty string appear, and should it count?
• Is input order required in the output?
• For the variant, must the two pieces be different words?

What a strong answer covers

• A hash set of words, then for each word a word-break check: dp[i] is true when the prefix of length i can be split into words, excluding the whole word itself as one piece.
• Cost: O(L²) substring checks per word of length L, fine with L <= 30; or sort by length and only use shorter words.
• A trie as an alternative that walks prefixes without building substrings.
• The two-piece variant in O(L) splits per word.
• Edge cases: single-letter words, the empty string, a word that is a prefix of another, many short words that blow up naive recursion without memoization.

Follow-ups

• Return the split for each word, using the fewest pieces.
• The list is huge and stored on disk. How do you process it?
• Count, for each word, how many different splits it has.