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)