Given a list of words, you need to find all the concatenated words in the list. A concatenated word is defined as a word that can be formed by concatenating at least two other words from the given list.
Table of Contents
Sample Input/Output:
Let’s consider a sample input:
words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]
Expected Output:
["catsdogcats", "dogcatsdog", "ratcatdogcat"]
Explanation:
In the given list of words, “catsdogcats” can be formed by concatenating “cats”, “dog”, and “cats”. Similarly, “dogcatsdog” can be formed by concatenating “dog”, “cats”, and “dog”, and “ratcatdogcat” can be formed by concatenating “rat”, “cat”, “dog”, and “cat”.
Time and Space Complexity:
Let n be the total number of words, and m be the average length of the words.
The time complexity of the solution will be O(n * m^2), where we perform a double loop over the list of words and check for possible concatenations. The inner loop involves substring checks, which take O(m) time.
The space complexity will be O(n) to store the result list of concatenated words.
C++ Solution:
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;
bool canFormWord(string word, unordered_set<string>& wordSet) {
if (wordSet.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 = i - 1; j >= 0; --j) {
if (dp[j] && wordSet.find(word.substr(j, i - j)) != wordSet.end()) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
vector<string> result;
unordered_set<string> wordSet(words.begin(), words.end());
for (string word : words) {
wordSet.erase(word); // Remove the word from the set to prevent self-concatenation
if (canFormWord(word, wordSet)) {
result.push_back(word);
}
wordSet.insert(word); // Add the word back to the set
}
return result;
}
int main() {
vector<string> words = {"cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"};
vector<string> result = findAllConcatenatedWordsInADict(words);
cout << "Concatenated words:\n";
for (string word : result) {
cout << word << endl;
}
return 0;
}
In this implementation, we use a helper function canFormWord that checks whether a given word can be formed by concatenating other words in the wordSet. The function uses dynamic programming to determine if the word can be split into other words in the set.
The main function findAllConcatenatedWordsInADict iterates through each word in the given list and removes the word from the wordSet before checking if it can be formed by concatenating other words. After the check, the word is added back to the wordSet to allow future concatenations.
The output will be:
Concatenated words:
catsdogcats
dogcatsdog
ratcatdogcat