Concatenated Words

Given an array of strings words (without duplicates), return all the concatenated words in the given list.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words (not necessarily distinct) from the given array.

Examples

Example 1:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]

Explanation: "catsdogcats" can be formed by "cats" + "dog" + "cats". "dogcatsdog" can be formed by "dog" + "cats" + "dog". "ratcatdogcat" can be formed by "rat" + "cat" + "dog" + "cat".

Example 2:

Input: words = ["cat","dog","catdog"]

Output: ["catdog"]

Explanation: "catdog" can be formed by concatenating "cat" and "dog".

Example 3:

Input: words = ["a","b","ab","abc"]

Output: ["ab"]

Explanation: "ab" can be formed by concatenating "a" and "b". "abc" cannot be fully formed from other words in the list.

Constraints

• 1 <= words.length <= 10⁴
• 1 <= words[i].length <= 30
• words[i] consists of only lowercase English letters
• All the strings of words are unique