DSA problem
Concatenated Words
Given an array of strings words (without duplicates), return all the concatenated words in the given list. A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
For example, if the input contains "cat", "dog", and "catdog", then "catdog" is a concatenated word because it splits into "cat" + "dog". A word formed by a single shorter word does not count — there must be at least two parts. A word does not count as a part of itself.
The brute-force approach is to test every word against every pair of substrings, which is prohibitively slow. A faster idea sorts words by length and uses DP per word: for each suffix position, check if the prefix ending there is a previously inserted word. Combined with a Trie this gives a very efficient solution.
The optimal strategy uses a Trie augmented with a memoized DFS. Sort words by length ascending so any potential building block of a word is processed before the word itself. For each word w, walk the Trie character by character — whenever we encounter a Trie node marked as a word ending, we have one valid split, and we recurse on the remaining suffix to ask "can the rest also be expressed as ≥ 1 concatenation?". A memo keyed by suffix index prevents exponential blow-up. Finally, insert w itself into the Trie so longer words can use it as a building block.
Examples
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]["catsdogcats","dogcatsdog","ratcatdogcat"]words = ["cat","dog","catdog"]["catdog"]words = ["a","b","ab","abc"]["ab"]Constraints
- 1 <= words.length <= 10^4
- 1 <= words[i].length <= 30
- words[i] consists of only lowercase English letters.
- 0 <= sum of words[i].length <= 10^5
- All the strings of words are unique.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.