Concatenated Words
Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words (not necessarily distinct) in the given array.
Example 1
Input
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]Output
["catsdogcats","dogcatsdog","ratcatdogcat"]"catsdogcats" can be formed by "cats", "dog", and "cats"; "dogcatsdog" by "dog", "cats", and "dog"; and "ratcatdogcat" by "rat", "cat", "dog", and "cat".
Example 2
Input
words = ["cat","dog","catdog"]Output
["catdog"]"catdog" is a concatenated word because it can be formed by "cat" and "dog".
Constraints
- 1 <= words.length <= 10^4
- 1 <= words[i].length <= 30
- words[i] consists of only lowercase English letters.
- All the strings of
wordsare unique. - 1 <= sum(words[i].length) <= 10^5