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) <= 105Problem Overview: You are given a dictionary of unique words. The task is to return all words that can be formed by concatenating at least two shorter words from the same dictionary. Each word can reuse other dictionary entries, but the concatenated word itself cannot be counted as its own component.
Approach 1: Trie + Depth-First Search (O(N * L^2) time, O(N * L) space)
This approach stores all words in a trie and checks each word using depth-first search. Starting from index 0, traverse the trie character by character. Whenever you reach a terminal node (a complete word), recursively attempt to match the remaining suffix. If the DFS reaches the end of the string after using at least two words, the word is valid. The trie allows fast prefix checks while DFS explores possible split points. This method works well when many words share prefixes because trie traversal avoids repeated substring lookups.
The key idea is treating the word as a sequence of smaller dictionary prefixes. The trie ensures prefix lookups happen in O(L) time, while DFS handles branching splits. Memoization on indices can further reduce repeated work when the same suffix is evaluated multiple times.
Approach 2: Dynamic Programming (O(N * L^2) time, O(L) space per word)
This solution treats the problem like a classic word break variant using dynamic programming. Sort words by length so shorter words are processed first. For each word, build a boolean DP array where dp[i] indicates whether the prefix ending at index i can be formed using previously processed words. Iterate over all split points j < i and check if dp[j] is true and the substring word[j:i] exists in a hash set.
If the final index becomes reachable and the word uses at least two components, it is a concatenated word. After evaluation, add the word to the dictionary so longer words can reuse it. Sorting ensures each word only depends on smaller ones, preventing self-construction. This approach is straightforward and relies heavily on efficient substring membership checks.
Recommended for interviews: The dynamic programming approach is usually expected because it mirrors the classic Word Break pattern and is easier to reason about during an interview. Implementing trie + DFS demonstrates stronger understanding of prefix structures and search strategies, which can be useful when the dictionary has heavy prefix overlap. Showing the DP baseline first and then discussing trie optimization demonstrates strong problem-solving depth.
This approach involves using a Trie data structure to store all words. We then perform a DFS to check if a word can be formed using other words in the trie. The main advantage of using a Trie is that it provides an efficient way to store and look up words simply by traversing nodes based on each character of the word.
We will mark nodes in the Trie that represent the end of a word and during DFS checks if the current segment of the word is in the Trie.
In the C solution, we create a Trie with nodes for each letter and a boolean flag indicating the end of a word. We add all the words into the Trie and then use a depth-first search (DFS) function to check if a given word can be constructed by concatenating other words in the Trie. If it can be constructed, it is added to the results list.
Time Complexity: O(n * m^2), where n is the number of words and m is the average length of the words. The DFS function can make at most m calls for each word.
Space Complexity: O(n * m) for storing the Trie, where n is the number of words and m is the average length of the words.
In this approach, dynamic programming (DP) is used to efficiently solve the problem of finding concatenated words. The idea is to treat each word as a state and store the results of subproblems to avoid repeated calculations. We iterate over each word and for each segment of the word, check if it can be split into valid sub-words based on previously computed results in the DP array.
This can be visualized as using a DP boolean array where each index represents if the word up to that index can be segmented into valid words in the list. This method is beneficial in reducing the number of redundant calculations.
The C solution uses a hashed linked list structure to store words and checks if each word is a concatenated word using dynamic programming. A boolean array is used to record which parts of the word can be formed by other words. The solution attempts to hash words into buckets and checks for matches to segment words.
Time Complexity: O(n * m^2), where n is the number of words and m is the average length of the words. The space used for the dp array and hash table is the main contributor.
Space Complexity: O(n * m) due to hash table entry needs.
| Approach | Complexity |
|---|---|
| Trie and Depth-First Search (DFS) | Time Complexity: O(n * m^2), where n is the number of words and m is the average length of the words. The DFS function can make at most m calls for each word. Space Complexity: O(n * m) for storing the Trie, where n is the number of words and m is the average length of the words. |
| Dynamic Programming | Time Complexity: O(n * m^2), where n is the number of words and m is the average length of the words. The space used for the dp array and hash table is the main contributor. Space Complexity: O(n * m) due to hash table entry needs. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Trie + DFS | O(N * L^2) | O(N * L) | Large dictionaries with shared prefixes where trie prefix lookups reduce repeated substring checks |
| Dynamic Programming (Word Break style) | O(N * L^2) | O(L) | General interview solution; simpler implementation using hash set and prefix DP |
Concatenated Words - Leetcode 472 - Python • NeetCodeIO • 25,183 views views
Watch 9 more video solutions →Practice Concatenated Words with our built-in code editor and test cases.
Practice on FleetCode