# Concatenated Words
**Difficulty:** HARD
[External](https://leetcode.com/problems/concatenated-words)
Canonical: https://scaleengineer.com/dsa/problems/concatenated-words
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Array, String, Trie
**Companies:** [eBay](https://scaleengineer.com/companies/ebay)
---
## Problem
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 (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 <= 104`
* `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) <= 105`

# Approaches
## Brute-Force Recursion
This approach checks each word in the input list to see if it can be formed by concatenating other words from the list. For every word, it uses a standard brute-force recursive method to solve the 'Word Break' problem. The dictionary for the word break check consists of all other words in the list.
**Time:** O(N * 2^L). For each of the N words, the `canBreak` function can take exponential time in the worst case, roughly O(2^L), where L is the length of the word. The set modifications take O(L) each. · **Space:** O(N * L + L). O(N * L) for storing the dictionary set, where N is the number of words and L is the average word length. O(L) for the recursion stack depth.
**Pros:** Simple to understand and implement the recursive logic.
**Cons:** Extremely inefficient due to the lack of memoization.; The number of recursive calls grows exponentially with the length of the word, leading to a 'Time Limit Exceeded' error on most platforms.; Repeatedly computes the result for the same subproblems.
### Explanation
The fundamental idea is to treat this as a series of 'Word Break' problems. For each word, we want to determine if it can be segmented using a dictionary composed of the *other* words in the list. This ensures that the word is formed by at least two shorter words.

The brute-force recursion explores all possible ways to segment a word. For a word `s`, it tries every possible prefix. If a prefix is a valid word in the dictionary, it recursively calls itself on the remaining suffix. This process continues until the suffix is empty (a successful segmentation) or all possibilities are exhausted.

Because this method does not store the results of subproblems (e.g., whether a particular suffix can be segmented), it re-computes the same information multiple times, leading to an exponential time complexity.

```java
public List<String> findAllConcatenatedWordsInADict(String[] words) {
    List<String> result = new ArrayList<>();
    Set<String> dictionary = new HashSet<>(Arrays.asList(words));

    for (String word : words) {
        dictionary.remove(word); // Temporarily remove the word itself
        if (canBreak(word, dictionary)) {
            result.add(word);
        }
        dictionary.add(word); // Add it back for the next iteration
    }
    return result;
}

private boolean canBreak(String s, Set<String> dictionary) {
    if (s.isEmpty()) {
        return true; // Successfully segmented
    }

    // Check every possible prefix
    for (int i = 1; i <= s.length(); i++) {
        String prefix = s.substring(0, i);
        if (dictionary.contains(prefix)) {
            // If prefix is a word, recursively check the rest of the string
            if (canBreak(s.substring(i), dictionary)) {
                return true;
            }
        }
    }

    return false; // No segmentation found
}
```
### Algorithm
- For each `word` in the input array `words`:
  - Create a dictionary `Set` containing all words from the input array except for the current `word`.
  - Call a recursive helper function `canBreak(current_word, dictionary)` to check if the `current_word` can be segmented into a sequence of one or more words from the temporary dictionary.
  - The `canBreak(s, dict)` function works as follows:
    - Base Case: If `s` is empty, it means the previous prefix was a valid word, so return `true`.
    - Recursive Step: Iterate from `i = 1` to `s.length()`. Split `s` into `prefix = s.substring(0, i)` and `suffix = s.substring(i)`.
    - If `prefix` is in the `dict` and `canBreak(suffix, dict)` returns `true`, then `s` can be broken down. Return `true`.
    - If the loop completes without finding a valid break, return `false`.
  - If `canBreak` returns `true`, add the `word` to the result list.

## Top-Down Dynamic Programming (Memoization)
This approach improves upon the brute-force recursion by using memoization (a top-down dynamic programming technique) to avoid re-computing results for the same substrings. For each word, we recursively check if it can be segmented into at least two smaller words from the dictionary, storing the outcomes of these checks to speed up future calculations.
**Time:** O(N * L^3). For each of N words, we solve the Word Break problem. With memoization, this takes O(L^3) because there are O(L) subproblems (suffixes), and each takes O(L^2) work (looping and substring operations). · **Space:** O(N * L). O(N * L) for the dictionary set and another O(N * L) in the worst case for the memoization map.
**Pros:** Significantly faster than the brute-force approach.; Correctly handles the 'at least two words' constraint in an elegant way.; Conceptually equivalent to a bottom-up DP but can be more intuitive to write.
**Cons:** The time complexity of O(L^3) per word might be too slow if the word lengths are large, although it's acceptable for the given constraints.; The space complexity for the memoization map can be significant if words have many unique substrings.
### Explanation
This method still iterates through each word and checks if it can be segmented, but the check itself is optimized. We use a hash map, `memo`, to store whether a given substring can be formed by other words. When the function is called for a substring, it first checks the `memo` map. If the result is already there, it's returned instantly. Otherwise, the result is computed, stored in the map, and then returned.

The recursive function `isConcatenated` is designed to specifically check for a composition of *at least two* words. It does this by iterating through all possible split points of the word. If it finds a split `(prefix, suffix)` where `prefix` is a dictionary word and `suffix` is either a dictionary word or can be further broken down (recursive call), then the original word is confirmed to be a concatenated word.

```java
public List<String> findAllConcatenatedWordsInADict(String[] words) {
    Set<String> dictionary = new HashSet<>(Arrays.asList(words));
    List<String> result = new ArrayList<>();
    Map<String, Boolean> memo = new HashMap<>();

    for (String word : words) {
        if (isConcatenated(word, dictionary, memo)) {
            result.add(word);
        }
    }
    return result;
}

private boolean isConcatenated(String word, Set<String> dictionary, Map<String, Boolean> memo) {
    if (memo.containsKey(word)) {
        return memo.get(word);
    }

    // Try all possible splits into two non-empty parts
    for (int i = 1; i < word.length(); i++) {
        String prefix = word.substring(0, i);
        String suffix = word.substring(i);

        if (dictionary.contains(prefix)) {
            // Suffix can be a single word or another concatenated word
            if (dictionary.contains(suffix) || isConcatenated(suffix, dictionary, memo)) {
                memo.put(word, true);
                return true;
            }
        }
    }

    memo.put(word, false);
    return false;
}
```
### Algorithm
- Create a `HashSet` of all words for efficient lookups.
- For each `word` in the input array, check if it's a concatenated word.
- To perform the check, use a recursive helper function `isConcatenated(word, dictionary, memo)` that utilizes a memoization map (`memo`) to store results of subproblems.
- The `isConcatenated` function tries to split the `word` into a `prefix` and a `suffix` at every possible position.
- A word is concatenated if we can find a split where:
  - The `prefix` is a word in the dictionary, AND
  - The `suffix` is either also a word in the dictionary OR the `suffix` itself is a concatenated word (checked via a recursive call).
- The loop for splitting starts from index 1 and goes up to `length - 1` to ensure the word is broken into at least two non-empty parts.
- Store the result for each `word` in the `memo` map to avoid re-computation.

## Optimized DP with Trie and Sorting
This is the most efficient approach, which combines sorting, a Trie data structure, and dynamic programming. By sorting the words by length, we can build up our dictionary of valid words incrementally. When we check a word, we only need to test if it can be formed by the shorter words we have already processed. A Trie is used to store these shorter words, allowing for very efficient prefix lookups during the DP check.
**Time:** O(N log N + N * L^2). O(N log N) for sorting the words. Then, for each of the N words, we perform a DP check. The check involves two nested loops, both bounded by the word length L, giving O(L^2). Adding a word to the Trie takes O(L). · **Space:** O(N * L). The space is dominated by the Trie, which in the worst case stores all characters of all N words of average length L.
**Pros:** Most efficient time complexity.; The sorting and Trie combination provides a very clean way to handle the 'composed of shorter words' constraint without extra logic.; Avoids expensive substring operations within the main DP loop.
**Cons:** The implementation is more complex due to the use of a Trie and the specific DP logic.; The initial sorting step adds an O(N log N) factor to the time complexity.
### Explanation
The key insight is that any concatenated word must be formed from shorter words. By sorting the input array by word length, we ensure that when we process any given `word`, all of its potential constituent words have already been seen.

We use a Trie to maintain the dictionary of words seen so far. For each `word` from the sorted list, we perform a DP-based 'Word Break' check using the words currently in the Trie. 

The DP array `dp` of size `L+1` tracks if prefixes of the `word` can be formed. `dp[0]` is true. We iterate from `i = 0` to `L-1`. If `dp[i]` is true, it means the prefix `word[0...i-1]` is formable. From this point, we can try to form a longer prefix. We do this by starting a traversal from the root of the Trie with the characters `word[i], word[i+1], ...`. If this traversal path hits a node marking the end of a word at index `j`, it means `word[i...j]` is a valid word from our dictionary. We can then set `dp[j+1]` to true.

If `dp[word.length()]` is true at the end, the word is concatenated. Finally, we add the current `word` to the Trie to make it available for subsequent, longer words.

```java
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEndOfWord = false;
}

public List<String> findAllConcatenatedWordsInADict(String[] words) {
    Arrays.sort(words, (a, b) -> a.length() - b.length());
    
    List<String> result = new ArrayList<>();
    TrieNode root = new TrieNode();
    
    for (String word : words) {
        if (word.isEmpty()) continue;
        
        if (canForm(word, root)) {
            result.add(word);
        }
        addWord(word, root);
    }
    
    return result;
}

private boolean canForm(String word, TrieNode root) {
    int n = word.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;

    for (int i = 0; i < n; i++) {
        if (!dp[i]) continue;
        
        TrieNode curr = root;
        for (int j = i; j < n; j++) {
            char c = word.charAt(j);
            if (curr.children[c - 'a'] == null) {
                break; // No matching prefix in Trie
            }
            curr = curr.children[c - 'a'];
            if (curr.isEndOfWord) {
                dp[j + 1] = true;
            }
        }
    }
    return dp[n];
}

private void addWord(String word, TrieNode root) {
    TrieNode curr = root;
    for (char c : word.toCharArray()) {
        if (curr.children[c - 'a'] == null) {
            curr.children[c - 'a'] = new TrieNode();
        }
        curr = curr.children[c - 'a'];
    }
    curr.isEndOfWord = true;
}
```
### Algorithm
- First, sort the input `words` array by length in ascending order. This is a crucial optimization.
- Initialize an empty `result` list and a `Trie` data structure.
- Iterate through the sorted `words` array one by one.
- For each `word`:
  - Check if this `word` can be formed by concatenating words that are already present in the `Trie`. Since we are iterating in increasing order of length, the `Trie` will only contain words that are strictly shorter than the current `word`.
  - This check is a 'Word Break' problem solved using bottom-up DP. We use a `dp` array where `dp[i]` is true if the prefix of the word of length `i` can be segmented.
  - The DP state transition is optimized by traversing the `Trie` instead of using `substring` and `set.contains` repeatedly. For each position `i` where `dp[i]` is true, we traverse the `Trie` with characters from the word starting at `i`. If we find a complete word in the `Trie` ending at index `j`, we set `dp[j+1]` to true.
  - If the check confirms the word is concatenated (`dp[word.length()]` is true), add it to the `result` list.
  - After checking the word, add it to the `Trie` so it can be used to form longer words later in the iteration.

# Solutions
### Java

```java
class Trie { Trie [] children = new Trie [ 26 ]; boolean isEnd ; void insert ( String w ) { Trie node = this ; for ( char c : w . toCharArray ()) { c -= 'a' ; if ( node . children [ c ] == null ) { node . children [ c ] = new Trie (); } node = node . children [ c ]; } node . isEnd = true ; } } class Solution { private Trie trie = new Trie (); public List < String > findAllConcatenatedWordsInADict ( String [] words ) { Arrays . sort ( words , ( a , b ) -> a . length () - b . length ()); List < String > ans = new ArrayList <>(); for ( String w : words ) { if ( dfs ( w )) { ans . add ( w ); } else { trie . insert ( w ); } } return ans ; } private boolean dfs ( String w ) { if ( "" . equals ( w )) { return true ; } Trie node = trie ; for ( int i = 0 ; i < w . length (); ++ i ) { int idx = w . charAt ( i ) - 'a' ; if ( node . children [ idx ] == null ) { return false ; } node = node . children [ idx ]; if ( node . isEnd && dfs ( w . substring ( i + 1 ))) { return true ; } } return false ; } }
```

### CPP

```cpp
class Trie { public: vector < Trie *> children ; bool isEnd ; Trie () : children ( 26 ) , isEnd ( false ) {} void insert ( string w ) { Trie * node = this ; for ( char c : w ) { c -= 'a' ; if ( ! node -> children [ c ]) node -> children [ c ] = new Trie (); node = node -> children [ c ]; } node -> isEnd = true ; } }; class Solution { public: Trie * trie = new Trie (); vector < string > findAllConcatenatedWordsInADict ( vector < string >& words ) { sort ( words . begin (), words . end (), [ & ]( const string & a , const string & b ) { return a . size () < b . size (); }); vector < string > ans ; for ( auto & w : words ) { if ( dfs ( w )) ans . push_back ( w ); else trie -> insert ( w ); } return ans ; } bool dfs ( string w ) { if ( w == "" ) return true ; Trie * node = trie ; for ( int i = 0 ; i < w . size (); ++ i ) { int idx = w [ i ] - 'a' ; if ( ! node -> children [ idx ]) return false ; node = node -> children [ idx ]; if ( node -> isEnd && dfs ( w . substr ( i + 1 ))) return true ; } return false ; } };
```

### Python

```python
class Trie : def __init__ ( self ): self . children = [ None ] * 26 self . is_end = False def insert ( self , w ): node = self for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . is_end = True class Solution : def findAllConcatenatedWordsInADict ( self , words : List [ str ]) -> List [ str ]: def dfs ( w ): if not w : return True node = trie for i , c in enumerate ( w ): idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : return False node = node . children [ idx ] if node . is_end and dfs ( w [ i + 1 :]): return True return False trie = Trie () ans = [] words . sort ( key = lambda x : len ( x )) for w in words : if dfs ( w ): ans . append ( w ) else : trie . insert ( w ) return ans
```