# 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)
words.add(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[0] = 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))
# Code (C++)
Approach 1:
Approach 2: