Code Implementation

class Solution:
    def findAllConcatenatedWordsInADict(self, words):
        word_set = set(words)
        result = []

        def canForm(word):
            if not word: return False
            dp = [False] * (len(word) + 1)
            dp[0] = True
            for i in range(1, len(word) + 1):
                for j in range(0, i):
                    if dp[j] and word[j:i] in word_set:
                        if j == 0 and i == len(word):
                            continue
                        dp[i] = True
                        break
            return dp[len(word)]

        for word in words:
            word_set.remove(word)
            if canForm(word):
                result.append(word)
            word_set.add(word)
        return result
      

class Solution {
public:
    bool canForm(const string& word, unordered_set<string>& dict) {
        if (word.empty()) return false;
        vector<bool> dp(word.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= word.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && dict.count(word.substr(j, i - j))) {
                    if (j == 0 && i == word.size()) continue;
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[word.size()];
    }

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_set<string> dict(words.begin(), words.end());
        vector<string> result;
        for (const string& word : words) {
            dict.erase(word);
            if (canForm(word, dict)) result.push_back(word);
            dict.insert(word);
        }
        return result;
    }
};
      

import java.util.*;

public class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        List<String> result = new ArrayList<>();

        for (String word : words) {
            wordSet.remove(word);
            if (canForm(word, wordSet)) {
                result.add(word);
            }
            wordSet.add(word);
        }
        return result;
    }

    private boolean canForm(String word, Set<String> dict) {
        if (word.length() == 0) return false;
        boolean[] dp = new boolean[word.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= word.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(word.substring(j, i))) {
                    if (j == 0 && i == word.length()) continue;
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[word.length()];
    }
}
      

/**
 * @param {string[]} words
 * @return {string[]}
 */
var findAllConcatenatedWordsInADict = function(words) {
    const wordSet = new Set(words);
    const result = [];

    function canForm(word) {
        if (!word) return false;
        const dp = new Array(word.length + 1).fill(false);
        dp[0] = true;
        for (let i = 1; i <= word.length; i++) {
            for (let j = 0; j < i; j++) {
                if (dp[j] && wordSet.has(word.substring(j, i))) {
                    if (j === 0 && i === word.length) continue;
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[word.length];
    }

    for (const word of words) {
        wordSet.delete(word);
        if (canForm(word)) result.push(word);
        wordSet.add(word);
    }
    return result;
};
      

Problem Description

Given a list of strings words, return all concatenated words in the list. A concatenated word is defined as a string that is comprised entirely of at least two shorter words from the same list. Each word in the list can only be used as a whole (not split), and you cannot reuse the same word instance to form itself.

• Each word in words is non-empty and consists of lowercase English letters.
• You must not use the same word as both part and result (i.e., do not count a word as concatenated if it is just itself).
• Return all such concatenated words in any order.

Thought Process

At first glance, the problem seems to require checking, for each word, if it can be formed by joining together two or more other words from the list. The naive approach would be to try all possible ways to split each word and see if both parts exist in the list. However, this quickly becomes inefficient as the list grows, because the number of possible splits increases with word length.

To optimize, we can think of this as a variation of the classic "word break" problem, where we use dynamic programming to efficiently check if a word can be segmented into smaller words from a dictionary. The key is to avoid redundant computation and to handle the case where the word itself is in the dictionary (so we must not use the word to build itself).

Solution Approach

• Step 1: Build a set for fast lookup. Put all the words into a set (word_set) so we can check if a substring is a word in constant time.
• Step 2: For each word, temporarily remove it from the set. This prevents us from using the word itself in its own construction.
• Step 3: Use Dynamic Programming to check for concatenation.
  • For each word, create a boolean array dp of size len(word) + 1. dp[i] means "can the prefix of length i be formed by concatenating words from the set?"
  • Initialize dp[0] = True (the empty string is always "formable").
  • For each position i, check all previous positions j such that dp[j] is true and word[j:i] is in the set. If so, set dp[i] = True.
  • To ensure we use at least two words, skip the case where the entire word is matched as a single dictionary word.
• Step 4: Restore the word to the set after checking. This lets future words use it as a building block.
• Step 5: Collect and return all words that can be formed by concatenation.

This approach ensures each word is checked efficiently, leveraging dynamic programming and set lookups for speed.

Example Walkthrough

Let's consider words = ["cat","cats","dog","catsdog","dogcat","catdogcat"].

• For "catsdog":
  • Remove "catsdog" from the set.
  • Check all splits:
    • "cat" + "sdog" (no "sdog" in set)
    • "cats" + "dog" (both are in set!)
  • So "catsdog" can be formed by "cats" + "dog". Add to result.
• For "catdogcat":
  • Remove "catdogcat" from set.
  • Check splits:
    • "cat" + "dogcat" ("cat" in set, check "dogcat")
    • "dog" + "cat" (both in set)
  • Dynamic programming will find that "cat" + "dog" + "cat" forms "catdogcat". Add to result.
• Shorter words like "cat" or "dog" cannot be formed by concatenation, so they are skipped.

The result is ["catsdog","catdogcat"].

Time and Space Complexity

• Brute-force approach:
  • Would try all possible splits for each word, leading to exponential time complexity in the length of the word.
• Optimized approach (DP):
  • For each word of length L, dynamic programming checks all O(L^2) substrings.
  • For N words, total time is roughly O(N * L^2), where L is the average word length.
  • Space complexity is O(L) for the dp array, per word.
• Why? Because each substring check is constant time (using a set), and we iterate over all words.

Summary

The solution efficiently finds all concatenated words by leveraging dynamic programming and a hash set for fast lookups. By temporarily removing the word being checked from the set, we avoid false positives. The approach is scalable and elegant, avoiding exponential brute-force checks by reusing previously computed results and ensuring each word is checked in polynomial time relative to its length.