References:

• https://leetcode.com/problems/concatenated-words/

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

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`
• `0 <= words[i].length <= 1000`
• `words[i]` consists of only lowercase English letters.
• `0 <= sum(words[i].length) <= 105`
```class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
words = set(words)
memo = {}

def dfs(word):
if word in memo:
return memo[word]
memo[word] = False
for i in range(1, len(word)):
if word[:i] in words and (word[i:] in words or dfs(word[i:])):
memo[word] = True
break
return memo[word]

return [word for word in words if dfs(word)]```

Time complexity: , where is the length of the input word list and is the length of the longest word

Space complexity :

Previous Post

Next article