# 472 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 in the given array.

Example 1:

``````Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
``````

Example 2:

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

Constraints:

• `1 <= words.length <= 104`
• `1 <= words[i].length <= 30`
• `words[i]` consists of only lowercase English letters.
• All the strings of words are unique.
• `1 <= sum(words[i].length) <= 105`
 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 `````` ``````class Solution: def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]: res = [] words_dict = set(words) for word in words: words_dict.remove(word) if self.check(word, words_dict): res.append(word) words_dict.add(word) return res def check(self, word: str, d: Set[str]) -> bool: if word in d: return True for i in range(len(word), 0, -1): if word[:i] in d and self.check(word[i:], d): return True return False``````