Watch 10 video solutions for Concatenated Words, a hard level problem involving Array, String, Dynamic Programming. This walkthrough by Techdose has 22,728 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1041 <= words[i].length <= 30words[i] consists of only lowercase English letters.words are unique.1 <= sum(words[i].length) <= 105