Find All Words Formed by Concatenating Two or More Shorter Words in the List
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a list of distinct words. A word is *composite* if it can be split into two or more consecutive pieces such that every piece is itself a word in the list. The same word may be used as a piece more than once in a split. Return every composite word in the list.
In the reported interview this was a variant of a well-known problem whose exact changes were not recorded, and only the approach was discussed. This version states the standard form so that it can be run.
### Function Signature
```python
def composite_words(words: list[str]) -> list[str]:
```
### Rules
- A split of a word `w` is a sequence of two or more non-empty strings whose concatenation, in order, equals `w`. The word is composite if at least one of its splits uses only strings that appear in `words`.
- Every piece of a split is shorter than `w`, so a word can never use itself as a piece.
- Return the composite words in the order in which they appear in `words`. If no word is composite, return `[]`.
### Constraints
- `1 <= len(words) <= 10^4`
- `1 <= len(words[i]) <= 30`
- The total length of all words is at most `10^5`.
- Every word consists of lowercase English letters, and all words are distinct.
### Examples
**Example 1**
```text
Input: words = ["ab", "cd", "abcd", "abc", "dab", "abcdab", "cdcd"]
Output: ["abcd", "abcdab", "cdcd"]
```
`"abcd"` is `"ab" + "cd"`, `"abcdab"` is `"ab" + "cd" + "ab"`, and `"cdcd"` uses `"cd"` twice. Neither `"abc"` nor `"dab"` can be split into words from the list.
**Example 2**
```text
Input: words = ["x", "xy", "yz", "xxyz", "xyz"]
Output: ["xxyz", "xyz"]
```
`"xyz"` is `"x" + "yz"`, and `"xxyz"` is `"x" + "xyz"`. `"xy"` cannot be split, because `"y"` is not in the list.
**Example 3**
```text
Input: words = ["a", "bc", "abcd"]
Output: []
```
Any split of `"abcd"` needs a last piece ending in `"d"`, and the only word in the list that ends in `"d"` is `"abcd"` itself.
Overview: Given a list of distinct lowercase words, return, in input order, every word that can be split into two or more shorter words from the same list, with reuse allowed. The problem tests efficient string segmentation and dictionary lookups across a large word list.
You are given a list `words` of distinct words. A word `w` is **composite** if it can be split into two or more consecutive pieces such that every piece is itself a word in `words`. The same word may be used as a piece more than once in a split.
Implement `composite_words(words)` and return every composite word in the list.
**Rules**
- A split of a word `w` is a sequence of two or more non-empty strings whose concatenation, in order, equals `w`. The word is composite if at least one of its splits uses only strings that appear in `words`.
- Every piece of a split is shorter than `w`, so a word can never use itself as a piece.
- Return the composite words in the order in which they appear in `words`. If no word is composite, return an empty list `[]`.
**Example 1**
```text
Input: words = ["ab", "cd", "abcd", "abc", "dab", "abcdab", "cdcd"]
Output: ["abcd", "abcdab", "cdcd"]
```
`"abcd"` is `"ab" + "cd"`, `"abcdab"` is `"ab" + "cd" + "ab"`, and `"cdcd"` uses `"cd"` twice. Neither `"abc"` nor `"dab"` can be split into words from the list.
**Example 2**
```text
Input: words = ["x", "xy", "yz", "xxyz", "xyz"]
Output: ["xxyz", "xyz"]
```
`"xyz"` is `"x" + "yz"`, and `"xxyz"` is `"x" + "xyz"`. `"xy"` cannot be split, because `"y"` is not in the list. The output keeps the input order, so `"xxyz"` comes first.
**Constraints**
- `1 <= len(words) <= 10^4`
- `1 <= len(words[i]) <= 30`
- The total length of all words is at most `10^5`.
- Every word consists of lowercase English letters, and all words are distinct.
No count or length in this problem exceeds 2^31 - 1, so 32-bit integers suffice in every language.
Constraints
- 1 <= len(words) <= 10^4
- 1 <= len(words[i]) <= 30
- The total length of all words is at most 10^5.
- Every word consists of lowercase English letters, and all words are distinct.
Examples
Input: (['ab', 'cd', 'abcd', 'abc', 'dab', 'abcdab', 'cdcd'],)
Expected Output: ['abcd', 'abcdab', 'cdcd']
Explanation: Source example 1: 'abcd' = 'ab'+'cd', 'abcdab' = 'ab'+'cd'+'ab', 'cdcd' reuses 'cd'; 'abc' and 'dab' cannot be split.
Input: (['x', 'xy', 'yz', 'xxyz', 'xyz'],)
Expected Output: ['xxyz', 'xyz']
Explanation: Source example 2, multi-level chain: 'xyz' = 'x'+'yz' and 'xxyz' = 'x'+'xyz'; 'xy' fails because 'y' is absent. Input order is kept.
Hints
- A piece must be strictly shorter than the word being tested, so a word can never be built from itself, and a single-letter word is never composite.
- A valid split may reuse the same piece and may need three or more pieces; a first piece that matches can still lead to a remainder that cannot be covered.
- Every word has at most 30 letters, so the number of places where a single word can be cut is small.