Concatenated Words

Problem Statement

In the problem, we are provided with an array of strings named words, where each string is guaranteed to be unique. The task is to identify and return all those strings from the array that can be termed as "concatenated words". A concatenated word in this context is a string that can be formed by concatenating two or more shorter strings from the same array. These component strings can repeat and are not required to be distinct, but they must be shorter than the concatenated word itself.

Examples

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
• 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) <= 105

Approach and Intuition

To solve this problem and find all the concatenated words in the given list:

1. First, consider using a data structure to efficiently store and search for the presence of words. A set or a hashset can be ideal since it allows for average O(1) time complexity for lookups.

2. Since every word can potentially be made up of any combination of other words in the list, we can utilize dynamic programming or recursion with memoization to determine if a word can be broken down into smaller words. A dynamic programming table can be particularly useful, where dp[i] can represent whether the substring of the word up to the i-th index can be formed by concatenating words from the list.

3. For each word, break it down starting from the first character and check if the prefix exists in the list. If a prefix is found, recursively check if the remaining portion of the word can be split into valid shorter words from the list. For efficiency, only consider splitting words that are longer than the current prefix.

4. Use memoization to store results of previously encountered strings during the recursion. This will prevent recalculating for substrings multiple times and reduce the time complexity dramatically.

5. As each word in the list is processed, check if it can be segmented into at least two or more shorter words from the list. If it can, add this to the resultant list of concatenated words.

By iterating through each word and applying the above method, all concatenated words can be determined efficiently despite the potentially large input size, respecting the provided constraints.

Solutions

class Solution {
    bool searchSubset(const string& target, int idx, vector<bool>& seen,
                      const unordered_set<string>& dict) {
        if (idx == target.length()) return true;
        if (seen[idx]) return false;
        seen[idx] = true;
        for (int end = target.length() - (idx == 0 ? 1 : 0); end > idx; --end) {
            if (dict.count(target.substr(idx, end - idx)) &&
                searchSubset(target, end, seen, dict)) {
                return true;
            }
        }
        return false;
    }
    
public:
    vector<string> findConcatWords(vector<string>& wordsList) {
        unordered_set<string> dict(wordsList.begin(), wordsList.end());
        vector<string> concatenatedWords;
        for (const string& word : wordsList) {
            vector<bool> visited(word.size(), false);
            if (searchSubset(word, 0, visited, dict)) {
                concatenatedWords.push_back(word);
            }
        }
        return concatenatedWords;
    }
};