472. Concatenated Words - Explanation

Description

You are given an array of strings words (without duplicates), return all the concatenated words in the given list of words in any order.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words (not necessarily distinct) 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 <= 10,000
1 <= words[i].length <= 30
words[i] consists of only lowercase English letters.
All the strings of words are unique.
1 <= sum(words[i].length) <= 100,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force (Backtracking)

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        n = len(words)
        res = []
        wordSet = set(words)
        maxLen = 0
        for w in words:
            maxLen = max(maxLen, len(w))

        def dfs(concatWord, totLen):
            if len(concatWord) > 1:
                word = "".join(concatWord)
                if word in wordSet:
                    res.append(word)
                    wordSet.remove(word)

            for i in range(len(words)):
                if totLen + len(words[i]) > maxLen:
                    continue
                concatWord.append(words[i])
                dfs(concatWord, totLen + len(words[i]))
                concatWord.pop()

        dfs([], 0)
        return res

Time & Space Complexity

Time complexity: $O(m * n ^ n)$
Space complexity: $O(m * n)$

Where $n$ is the size of the string array $words$ and $m$ is the length of the longest word in the array.

2. Recursion

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        wordSet = set(words)

        def dfs(word):
            for i in range(1, len(word)):
                prefix, suffix = word[:i], word[i:]
                if ((prefix in wordSet and suffix in wordSet) or
                    (prefix in wordSet and dfs(suffix))
                ):
                    return True
            return False

        res = []
        for w in words:
            if dfs(w):
                res.append(w)
        return res

Time & Space Complexity

Time complexity: $O(n * m ^ 4)$
Space complexity: $O(n * m)$

Where $n$ is the size of the string array $words$ and $m$ is the length of the longest word in the array.

3. Dynamic Programming (Top-Down)

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        wordSet = set(words)
        dp = {}

        def dfs(word):
            if word in dp:
                return dp[word]

            for i in range(1, len(word)):
                prefix, suffix = word[:i], word[i:]
                if ((prefix in wordSet and suffix in wordSet) or
                    (prefix in wordSet and dfs(suffix))
                ):
                    dp[word] = True
                    return True
            dp[word] = False
            return False

        res = []
        for w in words:
            if dfs(w):
                res.append(w)
        return res

Time & Space Complexity

Time complexity: $O(n * m ^ 3)$
Space complexity: $O(n * m)$

Where $n$ is the size of the string array $words$ and $m$ is the length of the longest word in the array.

4. Dynamic Programming (Bottom-Up)

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        wordSet = set(words)
        res = []

        for word in words:
            m = len(word)

            dp = [False] * (m + 1)
            dp[0] = True

            for i in range(1, m + 1):
                for j in range(i):
                    if j == 0 and i == m:
                        continue
                    if dp[j] and word[j:i] in wordSet:
                        dp[i] = True
                        break

            if dp[m]:
                res.append(word)

        return res

Time & Space Complexity

Time complexity: $O(n * m ^ 3)$
Space complexity: $O(n * m)$

Where $n$ is the size of the string array $words$ and $m$ is the length of the longest word in the array.