Problem 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.
Key Insights
- A concatenated word can be constructed from other words in the list.
- We can use a set to store the words for O(1) average time complexity lookups.
- A depth-first search (DFS) approach can be employed to break down a word into its constituent parts.
- Dynamic programming can help in storing results of subproblems to avoid recomputation.
Space and Time Complexity
Time Complexity: O(N * L^2) where N is the number of words and L is the maximum length of a word.
Space Complexity: O(N * L) for the storage of the words in a set and for the recursion stack.
Solution
To solve the problem, we can use a set to store all the words for quick lookups. For each word in the list, we will try to break it down into smaller substrings and check if those substrings exist in the set. We can implement this using a depth-first search (DFS) approach with memoization to avoid redundant calculations. Each time we successfully break a word into at least two parts that are both found in the set, we classify it as a concatenated word.