Concatenated Words
Solve this Problemwords, return every word that can be built by concatenating at least two other, shorter words from the same list — reusing a word as many times as needed, in any order.
This is Word Break run once per word, with the rest of the same list playing the role of the dictionary — a word "counts" exactly when it's fully covered by pieces drawn from the shared trie. The only wrinkle: the word trivially "matches itself" as a single whole piece, and that doesn't count as a real concatenation, so that one specific match — the entire word, taken in one bite, starting from position zero — gets explicitly excluded. Everything else about the reachability walk is identical to Word Break.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ words.length ≤ 200 - ◆
1 ≤ words[i].length ≤ 30 - ◆
words consists of lowercase English letters, and every entry is distinct
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive Split with a Hash Set
BruteDrop every word into a hash set. For each word, recursively try every way to peel off a prefix that's also in the set, requiring at least two such pieces to cover the whole word (the whole word matching itself as a single piece doesn't count). With no memoization, the same starting position inside a word gets re-explored through every different earlier split — exponential in the word's own length in the worst case.
O(n · 2ᴸ)O(n · L)1class Solution {
2 public String[] findAllConcatenatedWords(String[] words) {
3 Set<String> wordSet = new HashSet<>(Arrays.asList(words));
4 List<String> result = new ArrayList<>();
5 for (String word : words) {
6 if (word.isEmpty()) continue;
7 if (canForm(word, wordSet, 0, 0)) {
8 result.add(word);
9 }
10 }
11 return result.toArray(new String[0]);
12 }
13
14 private boolean canForm(String word, Set<String> wordSet, int start, int count) {
15 if (start == word.length()) return count >= 2;
16 for (int end = start + 1; end <= word.length(); end++) {
17 String piece = word.substring(start, end);
18 if (wordSet.contains(piece) && canForm(word, wordSet, end, count + 1)) {
19 return true;
20 }
21 }
22 return false;
23 }
24}Optimal — Trie + DP Per Word
OptimalInsert every word into one shared trie. Then run the same reachability DP as Word Break, once per word: dp[i] means "the first i characters can be covered by pieces found in the trie." The only twist is one guard — matching the *entire* word as a single first-to-last piece doesn't count, since that would just be the word matching itself with zero real splits. Skip that one case, and dp[length] being true means at least two genuine pieces covered the word. N is the total characters across all words, L the longest one.
O(N · L)O(N)1class Solution {
2 static class TrieNode {
3 TrieNode[] children = new TrieNode[26];
4 boolean isEnd = false;
5 }
6
7 public String[] findAllConcatenatedWords(String[] words) {
8 TrieNode root = new TrieNode();
9 for (String word : words) {
10 TrieNode node = root;
11 for (char c : word.toCharArray()) {
12 int idx = c - 'a';
13 if (node.children[idx] == null) {
14 node.children[idx] = new TrieNode();
15 }
16 node = node.children[idx];
17 }
18 node.isEnd = true;
19 }
20
21 List<String> result = new ArrayList<>();
22 for (String word : words) {
23 int n = word.length();
24 boolean[] dp = new boolean[n + 1];
25 dp[0] = true;
26 for (int i = 0; i < n; i++) {
27 if (!dp[i]) continue;
28 TrieNode node = root;
29 for (int j = i; j < n; j++) {
30 int idx = word.charAt(j) - 'a';
31 if (node.children[idx] == null) break;
32 node = node.children[idx];
33 if (node.isEnd && !(i == 0 && j == n - 1)) {
34 dp[j + 1] = true;
35 }
36 }
37 }
38 if (dp[n]) result.add(word);
39 }
40 return result.toArray(new String[0]);
41 }
42}