Concatenated Words
Concatenated Words is a hard dynamic programming problem solved with the 1d dp pattern.
The best approach, optimal (word-break dp per word), runs in O(n · L³) time and O(n · L) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (recursive cutting) up.
Problem
You are given an array of distinct lowercase strings words. A concatenated word is a word from the list that can be written as two or more words from the same list placed one after another. The shorter words may repeat, and they must each be in words.
Return every concatenated word in words, in any order.
Examples
Example 1
- Input
words = ["sun", "flower", "sunflower", "rise", "sunrise", "sunflowerrise", "bed"]- Output
["sunflower", "sunrise", "sunflowerrise"]- Why
- sunflower = sun + flower, sunrise = sun + rise, and sunflowerrise = sun + flower + rise (or sunflower + rise).
Example 2
- Input
words = ["ab", "abab", "ababab", "b"]- Output
["abab", "ababab"]- Why
- abab is ab twice and ababab is ab three times. ab cannot be split because a is not in the list.
Example 3
- Input
words = ["cat", "dog"]- Output
[]- Why
- Neither word is made of other words from the list.
Constraints
1 <= words.length <= 10^41 <= words[i].length <= 30words[i]consists of lowercase English letters.- All strings in
wordsare distinct. 1 <= sum(words[i].length) <= 10^5
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (recursive cutting) | O(n · 2^L) | O(n · L) |
| Optimal (word-break DP per word) | O(n · L³) | O(n · L) |
1Brute force (recursive cutting)
O(n · 2^L)A word of length L has up to 2^(L-1) ways to be cut, and recursion may try them all.O(n · L)The hash set holds all words; recursion depth is at most L.Put all words in a hash set. For each word, try every prefix that is in the set and recurse on the rest of the word, counting pieces. A word is concatenated when the recursion reaches the end with at least two pieces. Nothing is remembered between calls, so the same suffix is explored again and again.
- Build a set of all words.
- For each word w, call canSplit(w, 0, 0).
- canSplit(w, start, pieces): if start == len, return pieces >= 2.
- Otherwise for each end in (start, len]: if w[start..end) is in the set and canSplit(w, end, pieces + 1), return true.
class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Set<String> dict = new HashSet<>(Arrays.asList(words));
List<String> result = new ArrayList<>();
for (String w : words) {
if (canSplit(w, 0, 0, dict)) result.add(w);
}
return result;
}
private boolean canSplit(String w, int start, int pieces, Set<String> dict) {
if (start == w.length()) return pieces >= 2;
for (int end = start + 1; end <= w.length(); end++) {
if (dict.contains(w.substring(start, end)) && canSplit(w, end, pieces + 1, dict)) return true;
}
return false;
}
}class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
words_set = set(words)
def can_split(w: str, start: int, pieces: int) -> bool:
if start == len(w):
return pieces >= 2
for end in range(start + 1, len(w) + 1):
if w[start:end] in words_set and can_split(w, end, pieces + 1):
return True
return False
return [w for w in words if can_split(w, 0, 0)]class Solution {
unordered_set<string> dict;
bool canSplit(const string& w, int start, int pieces) {
if (start == (int) w.size()) return pieces >= 2;
for (int end = start + 1; end <= (int) w.size(); end++) {
if (dict.count(w.substr(start, end - start)) && canSplit(w, end, pieces + 1)) return true;
}
return false;
}
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
dict = unordered_set<string>(words.begin(), words.end());
vector<string> result;
for (const string& w : words) {
if (canSplit(w, 0, 0)) result.push_back(w);
}
return result;
}
};function findAllConcatenatedWordsInADict(words) {
const dict = new Set(words);
const canSplit = (w, start, pieces) => {
if (start === w.length) return pieces >= 2;
for (let end = start + 1; end <= w.length; end++) {
if (dict.has(w.substring(start, end)) && canSplit(w, end, pieces + 1)) return true;
}
return false;
};
return words.filter(w => canSplit(w, 0, 0));
}2Optimal (word-break DP per word)
O(n · L³)For each word there are O(L²) cuts and each substring lookup hashes O(L) letters; L is at most 30.O(n · L)The hash set holds all words; dp needs L + 1 entries.Run the classic word-break DP on every word. dp[i] says whether the first i letters can be split into words from the set. To stop a word from matching itself as one piece, the cut w[0..len) is skipped. Each prefix is decided once, so the work per word is polynomial.
- Build a set of all words.
- For each word w of length L: dp[0] = true.
- For i from 1 to L, for j from 0 to i - 1: if dp[j] and w[j..i) is in the set and not (j == 0 and i == L), set dp[i] = true and stop.
- If dp[L] is true, add w to the result.
class Solution {
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Set<String> dict = new HashSet<>(Arrays.asList(words));
List<String> result = new ArrayList<>();
for (String w : words) {
int len = w.length();
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
if (j == 0 && i == len) continue;
if (dp[j] && dict.contains(w.substring(j, i))) {
dp[i] = true;
break;
}
}
}
if (dp[len]) result.add(w);
}
return result;
}
}class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
words_set = set(words)
result = []
for w in words:
n = len(w)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if j == 0 and i == n:
continue
if dp[j] and w[j:i] in words_set:
dp[i] = True
break
if dp[n]:
result.append(w)
return resultclass Solution {
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
unordered_set<string> dict(words.begin(), words.end());
vector<string> result;
for (const string& w : words) {
int len = w.size();
vector<bool> dp(len + 1, false);
dp[0] = true;
for (int i = 1; i <= len; i++) {
for (int j = 0; j < i; j++) {
if (j == 0 && i == len) continue;
if (dp[j] && dict.count(w.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
if (dp[len]) result.push_back(w);
}
return result;
}
};function findAllConcatenatedWordsInADict(words) {
const dict = new Set(words);
const result = [];
for (const w of words) {
const len = w.length;
const dp = new Array(len + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= len; i++) {
for (let j = 0; j < i; j++) {
if (j === 0 && i === len) continue;
if (dp[j] && dict.has(w.substring(j, i))) {
dp[i] = true;
break;
}
}
}
if (dp[len]) result.push(w);
}
return result;
}Edge cases to test
- A word built from the same shorter word repeated many times
- A word that is in the list must not count as a concatenation of just itself
- Single-letter words that can build almost everything else
- Many prefixes match but the rest of the word cannot be split (for example
aaaa…abwith onlyaandaaavailable)
Hints
Hint 1
For one word this is the word-break question: can it be cut into pieces that are all in the dictionary? The extra rule is that the word itself is not allowed as the only piece.
Hint 2
Plain recursion that tries every cut explodes on words like aaaaaaaa…b. Remember, for each position, whether the suffix (or prefix) up to there can be split.
Hint 3
Let dp[i] be true when the first i letters can be split into dictionary words. A word qualifies when dp[len] is true using at least two pieces.
FAQ
What is the best time complexity for Concatenated Words?
Optimal (word-break DP per word) runs in O(n · L³) time and O(n · L) extra space. For each word there are O(L²) cuts and each substring lookup hashes O(L) letters; L is at most 30.
Which pattern does Concatenated Words use?
It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).
Is there a brute force solution for Concatenated Words?
Yes. Brute force (recursive cutting) takes O(n · 2^L) time and O(n · L) space. Put all words in a hash set.
Which edge cases should I test for Concatenated Words?
A word built from the same shorter word repeated many times; A word that is in the list must not count as a concatenation of just itself; Single-letter words that can build almost everything else; Many prefixes match but the rest of the word cannot be split (for example aaaa…ab with only a and aa available).