Concatenated Words
Hard · Tries · Array · String · Dynamic Programming · Depth-First Search · Trie
Problem
You are given an array of distinct strings words. A concatenated word is a string in words that can be written entirely as a concatenation of at least two shorter words from the same array. Pieces may repeat: a word can be used more than once.
Return all concatenated words in words, in any order.
Examples
Input: words = ["sun","flower","sunflower","sunsun","flow","er","sunflowers"] Output: ["flower","sunflower","sunsun"]
"flower" = flow + er, "sunflower" = sun + flower, "sunsun" uses "sun" twice. Nothing supplies the trailing "s" of "sunflowers".
Input: words = ["a","b","ab","abc"] Output: ["ab"]
"ab" = a + b, but "abc" would need a piece for "c".
Input: words = ["cat","dog"] Output: []
A word made of one piece (itself) does not count.
Constraints
- 1 <= len(words) <= 10^4
- 1 <= len(words[i]) <= 30
- words[i] consists of lowercase English letters
- All strings in words are distinct
- 1 <= sum of len(words[i]) <= 10^5
Approaches
- Word break trying every word at every position — time O(n² · L²), space O(L)
Follow-up
With a trie of the known words, the DP can walk forward from each reachable position letter by letter and stop as soon as no word continues, which avoids hashing substrings that cannot match.
Related problems
Start free on Cariara · Coding problems · System design studio
