> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0472-concatenated-words.md).

# 0472. Concatenated Words

<https://leetcode.com/problems/concatenated-words>

## Description

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`

## ac1: dp

similar to #139 work break. careful about "at least 2 words"

```java
class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> res = new ArrayList<>();
        // edge cases
        if (words == null || words.length < 2) return res;

        Set<String> set = new HashSet<>();
        for (String s : words) set.add(s);

        for (String s : words) {
            if (wordbreak(set, s)) 
                res.add(s);
        }

        return res;
    }

    private boolean wordbreak(Set<String> set, String s) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        int cnt = 0;  // comprise of at least 2 words
        for (int i = 1; i < dp.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    cnt++;
                    if (j == 0 && i == s.length()) cnt = 1;  // only single word
                    break;
                }
            }
        }
        return dp[dp.length-1] && cnt > 1;
    }
}
```

## ac2: trie

```java
class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> res = new ArrayList<>();
        // edge cases
        if (words == null || words.length < 2) return res;

        TrieNode root = new TrieNode();
        for (String s : words) {
            if (s.length() == 0) continue; // edge case
            add(root, s);
        }

        for (String s : words) {
            if (validate(root, s, 0)) res.add(s);
        }

        return res;
    }
    private boolean validate(TrieNode root, String s, int start) {
        TrieNode r = root;
        for (int i = start; i < s.length(); i++) {
            int pos = s.charAt(i) - 'a';
            if (r.next[pos] == null) return false;
            r = r.next[pos];
            if (r.isWord) {
                if (validate(root, s, i+1)) return true;
            }
        }
        return r.isWord && start != 0;
    }
    private void add(TrieNode root, String s) {
        TrieNode r = root;
        for (int i = 0; i < s.length(); i++) {
            int pos = s.charAt(i) - 'a';
            if (r.next[pos] == null) r.next[pos] = new TrieNode();
            r = r.next[pos];
        }
        r.isWord = true;
    }
}

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    boolean isWord = false;
}

/*
Time complexity:
1) Build trie: O(nk), n for words.size(), k for avg length of words.
2) Validate: O(nk).
Space: Trie worst case n*k, where no word share same branch in trie.
*/
```