Concatenated Words
Understanding the Problem
We have a list of words, and we need to find which ones can be built by joining two or more other words from the same list. The word "catsdogcats" is concatenated because you can break it into "cats" + "dog" + "cats", and all three pieces exist in the input array.
The pieces don't need to be distinct: "dogcatsdog" uses "dog" twice. A word must be formed from at least two pieces, so it does not count as a concatenation of itself, and every piece is strictly shorter than the word it builds.
Checking whether a single word can be decomposed into dictionary words is the Word Break problem (LeetCode 139). This problem runs Word Break on every word in the array, using the rest of the array as the dictionary.
Key Constraints:
words.length <= 10^4→ We can afford to process each word individually, as long as per-word work is small.words[i].length <= 30→ Individual words are short, so any per-character DP or Trie traversal is bounded by 30 steps, not thousands.sum(words[i].length) <= 10^5→ Total character budget is modest. Building a Trie or hash set of all words is cheap.
Approach 1: Brute Force Recursion
Intuition
For each word, try to break it into pieces where every piece exists in the word set, using recursion. At each step, try every possible prefix of the remaining string. If the prefix is in the word set, recurse on the suffix.
A concatenated word needs at least two pieces, so the recursion also tracks how many pieces it has used. If it consumes the entire string with two or more pieces, the word is concatenated.
Algorithm
- Add all words to a HashSet for O(1) lookups.
- For each word in the array, call a recursive helper that tries to decompose it.
- In the helper, iterate through all possible split positions (1 to length).
- If the prefix exists in the set, recurse on the suffix.
- If we reach the end of the string and have used at least 2 pieces, return true.
- Collect all words that return true.
Visualization and Code
Loading animation...
- Time Complexity: O(n * 2^L) in the worst case, where n is the number of words and L is the maximum word length. The recursion can branch at every character position, leading to exponential possibilities. In practice, branching is limited because most prefixes are not in the set.
- Space Complexity: O(N + L), where N is the total number of characters across all words (at most 10^5). The hash set stores every word, and the recursion goes at most L levels deep.
The recursion re-explores the same suffix many times: once a position has been shown undecomposable, every later path that reaches it repeats the failed work. The next approach computes the answer for each position once, bottom-up.
Approach 2: Dynamic Programming (Word Break)
Intuition
This approach runs Word Break (LeetCode 139) on each word, using the entire input array as the dictionary.
For a single word of length L, define dp[i] = true if the first i characters of the word can be formed by concatenating one or more words from the set. The base case is dp[0] = true (the empty prefix). For each position i, look back at every position j < i and check whether dp[j] is true and the substring word[j..i] is in the set.
Standard Word Break accepts a single piece, but a concatenated word needs at least two. The DP enforces this by skipping the transition with j=0 and i=L, which would match the whole word as one piece. And since no word is longer than 30 characters, each position only needs to look back at most 30 characters.
Skipping the single transition j=0, i=L is enough to enforce the two-piece minimum. Any other path to dp[L] = true passes through an intermediate index j with 0 < j < L and dp[j] = true, so the decomposition contains at least two pieces.
The break after setting dp[i] = true is a small optimization: once position i is known to be reachable, there is no need to find other splits that reach it.
Algorithm
- Add all words to a HashSet.
- For each word, run the following DP:
- Create a boolean array dp of size L+1, where dp[i] means "first i characters can be decomposed."
- Set dp[0] = true.
- For i from 1 to L: for each j from max(0, i - maxWordLen) to i-1, if dp[j] is true and word[j..i] is in the set, set dp[i] = true and move to the next i. Skip the pair j=0, i=L.
- If dp[L] is true, this word is concatenated.
- Return all concatenated words.
Visualization and Code
Loading animation...
- Time Complexity: O(n * L^3) where n is the number of words and L is the maximum word length (30). For each word, the DP has L outer iterations, up to L inner iterations, and each substring extraction plus hash lookup is O(L). Since L <= 30, this is at most about 27,000 operations per word.
- Space Complexity: O(N + L), where N is the total number of characters across all words. The hash set stores every word, and the DP array uses O(L) per word.
The DP creates a temporary substring for every hash lookup. A Trie removes that cost by matching against the dictionary character by character.
Approach 3: Trie + DFS
Intuition
Instead of storing words in a hash set and creating substrings to look them up, we build a Trie from all the words. Then for each word we want to check, we walk through the Trie character by character. Whenever we reach a node marked as end-of-word, there are two choices: continue extending the current word match (a longer dictionary word may share this prefix), or "restart" from the Trie root to begin matching the next piece. In "catsdogcats", the walk from position 0 reaches the end marker of "cat" at index 2 and the end marker of "cats" at index 3 on a single pass, and the DFS branches at both.
A visited array prevents re-exploring the same start position. If decomposing from position i failed once, it fails on every later visit.
The DFS carries a piece count, so memoizing failure per position needs a justification: could a position fail with one count but succeed with another? It cannot. Any position pos > 0 was reached by consuming at least one piece, so the two-piece minimum is met as long as the remaining suffix splits into one or more dictionary words. That condition depends only on pos, not on the count. A position that failed once fails always, and skipping it is safe.
Without the visited array, words built from many overlapping pieces (such as a long run of "a" with "a", "aa", "aaa" in the dictionary) would make the search exponential.
Algorithm
- Build a Trie from all words.
- For each word, run a DFS:
- Start at position 0 in the word and the root of the Trie.
- At each character, move to the corresponding Trie child.
- If the current Trie node is an end-of-word, recursively try to match the rest from the Trie root (new piece).
- If we've consumed the entire word with at least 2 pieces, return true.
- Use a visited array to skip positions we've already explored.
- Return all words that the DFS confirms as concatenated.
Visualization and Code
Loading animation...
- Time Complexity: O(N + n * L^2) where N is the total number of characters across all words, n is the number of words, and L is the maximum word length. Building the Trie takes O(N). For each word, the DFS visits each starting position at most once and walks at most L steps from each position.
- Space Complexity: O(N + L). The Trie stores all characters with 26 children per node. The visited array and recursion stack use O(L) per word.