Concatenated Words

Problem

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 <= 104
• 0 <= words[i].length <= 1000
• words[i] consists of only lowercase English letters.
• 0 <= sum(words[i].length) <= 105

Solution

/**
 * @param {string[]} words
 * @return {string[]}
 */
var findAllConcatenatedWordsInADict = function(words) {
    words = words.filter(w => w); // filter out empty string
    const set = {}; // set of elements in words
    for (const w of words) {
        set[w] = true;
    }

    const res = [];
    for (const w of words) {
        set[w] = false;
        if (wordBreak(w, set)) {
            res.push(w);
        }
        set[w] = true;
    }
    return res;
};

// check if s can be formed using words in set
var wordBreak = function(s, set) {
    const dp = Array(s.length + 1).fill(false);
    dp[0] = true;

    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            const substr = s.substring(j, i);
            if (dp[j] && set[substr]) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length];
};

We will implement a DP solution. Observe that this problem reduces down to the Word Break problem. Essentially, we test every word w in words using the wordBreak method whether each w can be formed using words in the set words\{w}.