376. Concatenated Words
You are given an array words of distinct, non-empty lowercase strings. Call an element a concatenated word if it can be written by gluing together two or more entries of words (an entry may be reused any number of times as a building block; since all words are distinct and non-empty, every building block is necessarily shorter than the word it helps build).
Return all concatenated words, in the order they appear in the input array.
Example 1:
Input: words = ["news", "paper", "newspaper", "week", "day", "weekday", "newsweekday"]
Output: ["newspaper", "weekday", "newsweekday"]
Explanation: "newspaper" = "news" + "paper", "weekday" = "week" + "day", and "newsweekday" = "news" + "week" + "day". The other four words cannot be built from two or more list entries.
Example 2:
Input: words = ["ab", "cd", "ef"]
Output: []
Explanation: No word can be assembled from the others, so the answer is empty.
Constraints:
- 1 ≤ n ≤ 10⁴
- 1 ≤ words[i].length ≤ 30
- words[i] consists of lowercase English letters only
- All words are distinct; the total length of all words does not exceed 10⁵
Hints:
For a single word, "can it be split into dictionary pieces?" is exactly Word Break: dp[i] says whether the suffix (or prefix) of length i can be segmented. The twist here is doing it for every word at once.
The "two or more pieces" rule is easy to enforce: just make sure the whole word itself is never usable as a single piece — either skip the full-length chunk in the DP, or only allow strictly shorter words as pieces.
Process words from shortest to longest and keep a growing dictionary of the words already processed. A concatenated word can only be built from shorter words, so everything it needs is already in the dictionary — and a trie over that dictionary lets each DP step walk prefixes character by character instead of hashing every substring.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: words = ["news", "paper", "newspaper", "week", "day", "weekday", "newsweekday"]
Expected output: ["newspaper", "weekday", "newsweekday"]