472.Concatenated Words
===
###### tags: `Hard`,`Array`,`String`,`DP`,`DFS`,`Trie`
[472. Concatenated Words](https://leetcode.com/problems/concatenated-words/)
### 題目描述
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` <= 10^4^
* 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)` <= 10^5^
### 解答
#### C++
##### 思路
1. 用DP檢查每個單字是否能用除了自己之外的單字來組成
```cpp=
class Solution {
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
unordered_set<string> s(words.begin(), words.end());
vector<string> ans;
for (auto word : words) {
int n = word.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
for (int i = 0; i < n; i++) {
if (!dp[i]) continue;
for (int j = i + 1; j <= n; j++) {
if (j - i < n && s.count(word.substr(i, j - i))) {
dp[j] = true;
}
}
if (dp[n]) {
ans.push_back(word);
break;
}
}
}
return ans;
}
};
```
> [name=Yen-Chi Chen][time=Mon, Jan 30, 2023]
### Reference
[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)