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