## # 472. Concatenated Words

Given a list of words (without duplicates), please write a program that returns all 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:

``````Input: ["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".
``````

Note:

• The number of elements of the given array will not exceed 10,000
• The length sum of elements in the given array will not exceed 600,000.
• All the input string will only include lower case letters.
• The returned elements order does not matter.

### # Solution

Approach 1: DP -- for each word, set up a table where table[i] is True if word[:i] can be concatenated. Time: `O(N * L^2)` where N is the length of the list, and L is the length of each word.

Approach 2: use a trie to store all words, and for each word, count the number of concatenations from the trie.

### # Code (Python)

Approach 1:

``````    def findAllConcatenatedWordsInADict(self, words):
words = set(words)
words.discard('') # no error raised if not in set
result = []
for word in words:
words.remove(word)
if self._can_concatenate_dp(word, words):
result.append(word)
return result

def _can_concatenate_dp(self, word, words):
# table[i] is True if word[:i] can be concatenated using words
table = [False for _ in range(len(word) + 1)]
table = True
for i in range(1, len(word) + 1):
for j in range(i):
if table[j]:
if word[j:i] in words:
table[i] = True
break
return table[-1]
``````

Approach 2:

``````class TrieNode:

def __init__(self):
self.is_word = False
self.children = {} # can also use an array of 26 chars

class Trie:

def __init__(self):
self.root = TrieNode()

def insert(self, word: 'str') -> 'None':
cur = self.root
for char in word:
if char not in cur.children:
cur.children[char] = TrieNode()
cur = cur.children[char]
cur.is_word = True

# (mostly) iterative solution
def num_concat(self, word, index):
if index >= len(word):
return 1
node = self.root
for i in range(index, len(word)):
if word[i] not in node.children:
return 0
if node.children[word[i]].is_word:
if i == len(word) - 1:
return 1
next = self.num_concat(word, i + 1)
if next > 0:
return next + 1
node = node.children[word[i]]
return 0

class Solution:
def findAllConcatenatedWordsInADict(self, words: 'List[str]') -> 'List[str]':
trie = Trie()
for word in words:
trie.insert(word)
return list(filter(lambda word: word and trie.num_concat(word, 0) > 1, words))
``````

Approach 1:

Approach 2: