# 472. 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`

Solution1:

Method 1: top-down DP (444 ms, beat 52%)
Let dp[i] = whether s[i:len(s)] can be segmented into a space-separated sequence of words, i=0,1,2,…, len(s).
The possible values of dp[i] are:
0 means s[i:len(s)] cannot be sucessfully segmented,
1 means s[i:len(s)] is in words and cannot be sucessfully segmented,
2 means s[i:len(s)] can be segmented into a space-spearated sequence of at least two words.

``````    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
def recursive(s, i, n):
if i in dp:
return dp[i]
j = i + 1
while j <= n:
if s[i:j] in word_set and recursive(s, j, n):
dp[i] = 2 if j < n else 1
return dp[i]
j += 1
dp[i] = 0
return dp[i]

word_set = set(words)
res = []
for w in words:
n = len(w)
dp = {n: 1}
if recursive(w, 0, n) > 1:
res.append(w)
return res``````

Solution2:

Method: implement same algorithm via Trie + DFS (1616 ms, beat 6.95%)(Time Limit Exceeded)

``````class TrieNode():
def __init__(self):
self.children = {}
self.isEnd = False

class Trie():
def __init__(self, words):
self.root = TrieNode()
for w in words:
if w:
self.insert(w)

def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.isEnd = True

class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
def dfs(node, i, w, space_inserted):
if i == len(w):
return node.isEnd and space_inserted
if node.isEnd:
if dfs(trie.root, i, w, True):
return True
if w[i] not in node.children:
return False
else:
return dfs(node.children[w[i]], i + 1, w, space_inserted)

trie = Trie(words)
res = []
for w in words:
if dfs(trie.root, 0, w, False):
res.append(w)
return res``````
Scroll to Top