Concatenated Words | Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

by

Given an array of string 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 <= 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

To solve this problem, you can use a combination of a Trie data structure and dynamic programming.

  • First, create a Trie data structure with all the words in the input array.
  • Next, for each word in the array, perform a depth-first search on the Trie to check if it can be formed by concatenating other words in the Trie.
  • Use dynamic programming to store the results of the search for each word, to avoid recalculating the same sub-problems multiple times.
  • Finally, return the list of words that can be formed by concatenating other words in the Trie.

The time complexity of this approach is O(n*L^2) where n is the number of words in the array and L is the maximum length of a word. The space complexity is O(nL) for storing the Trie and the dynamic programming array.

class Solution {
public:
    struct TrieNode {
        bool isEnd;
        unordered_map<char, TrieNode*> children;
        TrieNode() : isEnd(false) {}
    };
    TrieNode* root;
    vector<string> ans;
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        root = new TrieNode();
        for (string& word : words) {
            TrieNode* curr = root;
            for (char c : word) {
                if (!curr->children[c]) curr->children[c] = new TrieNode();
                curr = curr->children[c];
            }
            curr->isEnd = true;
        }
        unordered_map<string, bool> dp;
        for (string& word : words) {
            if (word.empty()) continue;
            dp.clear();
            dp[word] = true;
            if (search(root, dp, word)) ans.push_back(word);
        }
        return ans;
    }
    bool search(TrieNode* curr, unordered_map<string, bool>& dp, string& word) {
        for (int i = 0; i < word.size(); i++) {
            string suffix = word.substr(i);
            if (!curr->children[suffix[0]]) return false;
            curr = curr->children[suffix[0]];
            if (curr->isEnd && dp.count(suffix) == 0 && search(root, dp, suffix)) {
                dp[suffix] = true;
                return true;
            }
        }
        return false;
    }
};

Leave a Comment