# 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: