#472
Concatenated Words
candidate master · 1435 · lc hard +32 · verified · 49.7% accepted · 4,061 likes · top 37%
Description
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"]
Code
1
2
3