Is Concatenated Words easy or hard?

Concatenated Words is classified as a hard problem because it combines multiple concepts: string segmentation, dynamic programming, recursion, and efficient dictionary lookups. Handling edge cases like preventing a word from using itself also increases implementation complexity.

Concatenated Words Python/Java solution

In Python or Java, the typical solution builds a set of words and applies dynamic programming to test each word. Alternatively, a trie combined with DFS checks prefixes and recursively validates the remaining substring. Both implementations achieve roughly O(N * L^2) complexity.

How to solve Concatenated Words in O(n)?

A strict O(n) solution is not typical because each word must evaluate multiple substring splits. The closest practical approach is O(N * L^2) using dynamic programming or trie-based DFS. Optimizations such as memoization and prefix pruning reduce redundant checks but do not eliminate the quadratic dependence on word length.

What is the best approach for Concatenated Words?

The most common solution uses dynamic programming similar to the Word Break problem. Words are processed from shortest to longest, and a DP array checks whether each prefix can be formed from existing dictionary entries. This approach runs in about O(N * L^2) time where N is the number of words and L is the maximum word length.

Is Concatenated Words asked at Google/Amazon/Meta?

Concatenated Words is considered a hard string and dynamic programming problem and appears in advanced interview rounds at companies like Google, Amazon, and Meta. It tests knowledge of word segmentation, trie structures, recursion, and optimization techniques.

What data structure is used in Concatenated Words?

Common data structures include a trie for fast prefix lookup and a hash set for constant-time dictionary membership checks. Dynamic programming arrays are used to track valid word break positions, while DFS recursion explores possible concatenation splits.

What is the time complexity of Concatenated Words?

Most optimal solutions run in O(N * L^2) time. Each word of length L is checked by evaluating multiple split points, and substring membership checks occur against a dictionary or trie. Space complexity ranges from O(L) for DP to O(N * L) when storing all words in a trie.

Description Solution Video 12:00

472. Concatenated Words

Hard49.9% acceptance3 companies

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 <= 10⁴
1 <= words[i].length <= 30
words[i] consists of only lowercase English letters.
All the strings of words are unique.
1 <= sum(words[i].length) <= 10⁵

Asked at 3 companies

eBay Amazon Tiktok

Topics

12:00

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

472. Concatenated Words

Asked at 3 companies

Topics

Similar problems