Concatenated Words
Hard · trie
You are given a list words of different, non-empty lowercase words.
A word is built from the others if it can be cut into two or more consecutive parts so that every part is itself a word in words. The same word may be used for several parts, and a word is never allowed to count as its own single part.
Return every word of words that is built from the others, in the same order as they appear in words. Return an empty list if there are none.
Examples
Example 1
Input: words = ["cat", "dog", "catdog", "dogcatdog", "bird"]
Output: ["catdog", "dogcatdog"]
"catdog" is "cat" + "dog", and "dogcatdog" is "dog" + "cat" + "dog" (a word can be used twice).
Example 2
Input: words = ["sun", "moonsun", "sunsun", "moon"]
Output: ["moonsun", "sunsun"]
"moonsun" is "moon" + "sun" and "sunsun" is "sun" + "sun". "sun" and "moon" cannot be cut into smaller listed words.
Constraints
- 1 <= len(words) <= 5000
- 1 <= len(words[i]) <= 30
- words[i] contains only lowercase English letters
- All the words in words are different.