472. Concatenated Words

Given an array of strings words (without duplicates), return all the 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 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