Hard
Quiz
#472 Concatenated Words
APPROACH
Given an array of distinct strings words, find every word that is composed entirely by concatenating two or more shorter words (not necessarily distinct) that also appear in words. Return those words.
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"]
1 of 4
1:00
What is the optimal approach for this problem?