472. Concatenated Words

Description

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 (not necessarily distinct) 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

 

Solutions

Solution: Depth-First Search

• Time complexity: O(n*word.length²)
• Space complexity: O(n*word.length)

 

JavaScript

/**
 * @param {string[]} words
 * @return {string[]}
 */
const findAllConcatenatedWordsInADict = function (words) {
  const wordsSet = new Set(words);
  const memo = new Map();
  const result = [];

  const isConcatenatedWord = word => {
    if (memo.has(word)) return memo.get(word);

    for (let index = 0; index < word.length; index++) {
      const prefix = word.slice(0, index + 1);

      if (!wordsSet.has(prefix)) continue;
      const suffix = word.slice(index + 1);

      if (wordsSet.has(suffix) || isConcatenatedWord(suffix)) {
        memo.set(word, true);
        return true;
      }
    }
    memo.set(word, false);
    return false;
  };

  for (const word of words) {
    if (!isConcatenatedWord(word)) continue;
    result.push(word);
  }
  return result;
};