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:
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:
- The number of elements of the given array will not exceed
10,000 - The length sum of elements in the given array will not exceed
600,000. - All the input string will only include lower case letters.
- The returned elements order does not matter.
这道题给了一个由单词组成的数组，某些单词是可能由其他的单词组成的，让我们找出所有这样的单词。这道题跟之前那道Word Break十分类似，我们可以对每一个单词都调用之前那题的方法，我们首先把所有单词都放到一个unordered_set中，这样可以快速找到某个单词是否在数组中存在。对于当前要判断的单词，我们先将其从set中删去，然后调用之前的Word Break的解法，具体讲解可以参见之前的帖子。如果是可以拆分，那么我们就存入结果res中，参见代码如下：
解法一：
class Solution {
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
if (words.size() <= 2) return {};
vector<string> res;
unordered_set<string> dict(words.begin(), words.end());
for (string word : words) {
dict.erase(word);
int len = word.size();
if (len == 0) continue;
vector<bool> v(len + 1, false);
v[0] = true;
for (int i = 0; i < len + 1; ++i) {
for (int j = 0; j < i; ++j) {
if (v[j] && dict.count(word.substr(j, i - j))) {
v[i] = true;
break;
}
}
}
if (v.back()) res.push_back(word);
dict.insert(word);
}
return res;
}
};
下面这种方法跟上面的方法很类似，不同的是判断每个单词的时候不用将其移除set，而是在判断的过程中加了判断，使其不会判断单词本身是否在集合set中存在，而且由于对单词中子字符串的遍历顺序不同，加了一些优化在里面，使得其运算速度更快一些，参见代码如下：
解法二：
class Solution {
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
vector<string> res;
unordered_set<string> dict(words.begin(), words.end());
for (string word : words) {
int n = word.size();
if (n == 0) continue;
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 && dict.count(word.substr(i, j - i))) {
dp[j] = true;
}
}
if (dp[n]) {res.push_back(word); break;}
}
}
return res;
}
};
下面这种方法是递归的写法，其中递归函数中的cnt表示有其他单词组成的个数，至少得由其他两个单词组成才符合题意，参见代码如下：
解法三：
class Solution {
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
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;
}
bool helper(string& word, unordered_set<string>& dict, int pos, int cnt) {
if (pos >= word.size() && cnt >= 2) return true;
for (int i = 1; i <= (int)word.size() - pos; ++i) {
string t = word.substr(pos, i);
if (dict.count(t) && helper(word, dict, pos + i, cnt + 1)) {
return true;
}
}
return false;
}
};
类似题目：
参考资料：
https://discuss.leetcode.com/topic/72393/c-772-ms-dp-solution
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
