> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/472.-concatenated-words.md).

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

```
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:**<br>

1. The number of elements of the given array will not exceed `10,000`
2. The length sum of elements in the given array will not exceed `600,000`.
3. All the input string will only include lower case letters.
4. The returned elements order does not matter.

```cpp
// Use Dynamic Programming from 139. Word Break
bool helper(string word, unordered_set<string>& dict) {
    if (dict.empty()) return false;
    int n = word.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] && dict.count(word.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp.back();
}
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
    unordered_set<string> dict;
    vector<string> res;
    sort(words.begin(), words.end(), [](string& w1, string& w2) {
        return w1.length() < w2.length();
    });
    for (string word : words) {
        if (helper(word, dict)) res.push_back(word);
        dict.insert(word);
    }
    return res;
}
```

```cpp
// DFS
bool helper(string& word, unordered_set<string>& dict, int pos, int cnt) {
    if (pos >= word.length() && cnt >= 2) return true;
    for (int len = 1; len <= word.length() - pos; ++len) {
        string t = word.substr(pos, len);
        if (dict.count(t) && helper(word, dict, pos + len, cnt + 1))
            return true;
    }
    return false;
}
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) { // time: O(n^2); space: O(n)
    vector<string> res;
    unordered_set<string> dict(words.begin(), words.end());
    for (string word : words) {
        if (word.empty()) continue;
        if (helper(word, dict, 0, 0)) res.push_back(word);
    }
    return res;
}
```