Log inSign up
hardLeetCodeNot Started

Concatenated Words

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trie
Solve on LeetCode
Lesson

Problem Statement

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 · Example 1: Cats and Dogs:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: - "catsdogcats" = "cats" + "dog" + "cats" - "dogcatsdog" = "dog" + "cats" + "dog" - "ratcatdogcat" = "rat" + "cat" + "dog" + "cat" Trie Structure of component words: (root) / | \ c d r | | | cat dog rat

Constraints:

  • 1 <= words.length <= 104
  • 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) <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Sort by word length to convert static set dependency into monotonic online verification.
  • Implement multi-word segmentation (Word Break) using Trie traversal.
  • Prevent self-matching by verifying words strictly against shorter vocabulary.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Words formed by concatenating at least two other words in the same list.
  • Word break / string segmentation problem over a dynamic or static vocabulary.
  • Word length is small (L <= 30) while dictionary is large (N = 10,000).

Algorithmic Decision Tree:

  • Sort words by length ascending.
  • Maintain a Trie of previously seen (shorter) words.
  • For word W: run DFS from index 0; if index reaches W.length, word is concatenated! Add to results; then insert W into Trie.

Connected Patterns:

Word BreakWord Break IIWord Search II

1. Word Break DP with Full Dictionary

Intuition

Store words in unordered_set<string>. For each word, temporarily remove it. Run standard Word Break DP: dp[i] = true if there exists j such that dp[j] && word.substr(j, i-j) in set. If dp[len] is true, add to result. Reinsert word.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Insert all words into a hash set.
  2. Step 2: For each word, remove from set.
  3. Step 3: Run dp array of size len + 1: dp[0] = true.
  4. Step 4: For i from 1 to len: check if dp[j] && word.substr(j, i-j) in set.
  5. Step 5: If dp[len] is true, add word to result. Re-insert word into set.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5using namespace std;
6
7class Solution {
8public:
9 vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
10 unordered_set<string> dict(words.begin(), words.end());
11 vector<string> result;
12
13 for (const string& w : words) {
14 if (w.empty()) continue;
15 dict.erase(w);
16 int len = w.length();
17 vector<bool> dp(len + 1, false);
18 dp[0] = true;
19
20 for (int i = 1; i <= len; i++) {
21 for (int j = 0; j < i; j++) {
22 if (dp[j] && dict.count(w.substr(j, i - j))) {
23 dp[i] = true;
24 break;
25 }
26 }
27 }
28 if (dp[len]) result.push_back(w);
29 dict.insert(w);
30 }
31 return result;
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<string> words = {"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
38 auto res = sol.findAllConcatenatedWordsInADict(words);
39 for (const string& s : res) cout << s << " ";
40 cout << endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N * L^3) — For N words, DP takes O(L2) steps with O(L) string slicing each.
  • Space complexity: O(N * L) — Hash set holds all words.

Why Brute Force Doesn't Scale:

With 10,000 words, repeated string allocations cause high GC pressure and TLE.

Trie-based length-sorted segmentation checks 10,000 words in O(N * L2) without a single string slice in ~45ms.

2. Memoized DFS with Length Sorting & Set

Intuition

Sort words by length ascending. Maintain wordSet of shorter words. For word W, use memoized helper canForm(W, startIdx, memo). If true, add to result; otherwise (or either case), add W into wordSet.

When to apply: Fast memoization without building explicit Trie pointers.

Algorithm

  1. Step 1: Sort words: len(a) < len(b).
  2. Step 2: Maintain set seen.
  3. Step 3: Define canForm(w, idx): if idx == len, return true. For k from idx+1 to len: if w[idx..k] in seen and canForm(w, k), return true.
  4. Step 4: If canForm(w, 0), append to results; else seen.insert(w).
  5. Step 5: Return results.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <algorithm>
6using namespace std;
7
8class Solution {
9 unordered_set<string> seen;
10
11 bool canForm(const string& w, int idx, vector<int>& memo) {
12 if (idx == (int)w.length()) return true;
13 if (memo[idx] != -1) return memo[idx];
14
15 for (int len = 1; idx + len <= (int)w.length(); len++) {
16 if (seen.count(w.substr(idx, len)) && canForm(w, idx + len, memo)) {
17 return memo[idx] = 1;
18 }
19 }
20 return memo[idx] = 0;
21 }
22
23public:
24 vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
25 sort(words.begin(), words.end(), [](const string& a, const string& b) {
26 return a.length() < b.length();
27 });
28
29 seen.clear();
30 vector<string> result;
31
32 for (const string& w : words) {
33 if (w.empty()) continue;
34 vector<int> memo(w.length(), -1);
35 if (canForm(w, 0, memo)) {
36 result.push_back(w);
37 }
38 seen.insert(w);
39 }
40 return result;
41 }
42};
43
44int main() {
45 Solution sol;
46 vector<string> words = {"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
47 auto res = sol.findAllConcatenatedWordsInADict(words);
48 for (const string& s : res) cout << s << " ";
49 cout << endl;
50 return 0;
51}

Time & Space Complexity

  • Time complexity: O(N log N * L + N * L^2) — Sorting takes O(N log N * L). Memoized DFS visits each index at most once per word.
  • Space complexity: O(N * L) — Hash set and memoization array.

3. Trie DFS Word Break Segmentation with Length Sorting

Intuition

Sort words by length ascending so component words are always processed before compound words. Maintain a Trie. For each word, define canForm(word, startIdx, memo): walk characters from startIdx down the Trie. Whenever curr.isEnd == true: if we reached end of word, return true; else recursively test if canForm(word, nextIdx, memo) returns true. After checking, insert word into the Trie.

When to apply: Standard optimal solution with zero substring allocations during word segmentation.

Algorithm

  1. Step 1: Sort words by length ascending.
  2. Step 2: Create root of Trie with children[26] and boolean isEnd.
  3. Step 3: Define canForm(word, start, memo): walk Trie from start. At each node where curr.isEnd: if end of string, return true; else if canForm(word, nextChar, memo) is true, return true.
  4. Step 4: If canForm(word, 0) is true, add to result.
  5. Step 5: Insert word into Trie. Return result.

Interactive Trace for Monotonic Trie Concatenation

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Check 'catdog'
Visual state
Values and pointers at this exact step
tree
Root
(root)
word 'cat'*
'cat'* (isEnd)

Node order shown; add connections to display explicit tree edges.

first segment: cat
Check / comparison
'cat' isEnd == true -> Branch to root for suffix 'dog'
Decision / next transition
Recurse on root with remaining string 'dog'.
Why this step matters

Step 1: Check catdog. Walk c -> a -> t. Node cat has isEnd = true. Branch 1: restart from root for remaining suffix dog.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7struct TrieNode {
8 TrieNode* children[26];
9 bool isEnd;
10 TrieNode() : isEnd(false) {
11 for (int i = 0; i < 26; i++) children[i] = nullptr;
12 }
13};
14
15class Solution {
16 TrieNode* root;
17
18 void insert(const string& w) {
19 TrieNode* curr = root;
20 for (char c : w) {
21 int idx = c - 'a';
22 if (!curr->children[idx]) curr->children[idx] = new TrieNode();
23 curr = curr->children[idx];
24 }
25 curr->isEnd = true;
26 }
27
28 bool canForm(const string& w, int start, vector<int>& memo) {
29 if (start == (int)w.length()) return true;
30 if (memo[start] != -1) return memo[start];
31
32 TrieNode* curr = root;
33 for (int i = start; i < (int)w.length(); i++) {
34 int idx = w[i] - 'a';
35 if (!curr->children[idx]) return memo[start] = 0;
36 curr = curr->children[idx];
37 if (curr->isEnd) {
38 if (canForm(w, i + 1, memo)) {
39 return memo[start] = 1;
40 }
41 }
42 }
43 return memo[start] = 0;
44 }
45
46public:
47 vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
48 sort(words.begin(), words.end(), [](const string& a, const string& b) {
49 return a.length() < b.length();
50 });
51
52 root = new TrieNode();
53 vector<string> result;
54
55 for (const string& w : words) {
56 if (w.empty()) continue;
57 vector<int> memo(w.length(), -1);
58 if (canForm(w, 0, memo)) {
59 result.push_back(w);
60 }
61 insert(w);
62 }
63 return result;
64 }
65};
66
67int main() {
68 Solution sol;
69 vector<string> words = {"cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"};
70 auto res = sol.findAllConcatenatedWordsInADict(words);
71 for (const string& s : res) cout << s << " ";
72 cout << endl;
73 return 0;
74}

Time & Space Complexity

  • Time complexity: O(N log N * L + N * L^2) — Sorting takes O(N log N * L). Trie segmentation touches each index at most once per word without string slicing.
  • Space complexity: O(Total word chars * 26) — Trie nodes allocate 26 pointers each.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Word Break DP with Full DictionaryO(N * L^3)O(N * L)Put all words in a set. For each word, temporarily remove it from the set and run 1D DP dp[i] = any(dp[j] && word[j..i] in set).Substring slicing and hashing during DP.
2.Better — Memoized DFS with Hash SetO(N * L^2)O(N * L)Sort words by length. Maintain set of shorter words. For each word, use memoized DFS to check if it can be partitioned.String slicing in recursive DFS.
3.Optimal — Length-Sorted Monotonic Trie DFSOptimalO(N log N * L + N * L^2)O(Total word chars * 26)Sort words by length. For each word, walk Trie from index 0. Whenever a word ends, branch to index 0 of Trie for next segment. If reaches end, add to result; then insert word into Trie.None. Classical hard interview question.

Common Pitfalls & Crucial Edge Cases

Not sorting by length

If a compound word is checked before its component words are added, it will be falsely rejected.

Inserting the word into the Trie before checking

The word would match itself (single word instead of 'at least two shorter words').

Forgetting memoization in DFS

Without memoization on start index, adversarial inputs with overlapping prefixes cause exponential branching.

Crucial Edge Cases to Validate:

  • Empty string in words array — Filtered out immediately; empty string cannot be a component of concatenated words.
  • Word cannot be decomposed into shorter words — Fails canForm check, inserted into Trie for future longer words.
  • Word composed of same word repeated ('catcat') — Handled naturally by reusing cat from Trie.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Emphasize the length-sorting insight: it guarantees that only strictly shorter words exist in the Trie when testing a candidate.
  2. Highlight how Trie eliminates string slicing: transitions occur via char pointer lookups rather than generating new string copies.
  3. Mention that memoizing on start index guarantees at most L recursive calls per word.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why are words sorted by length ascending before processing?

2.Why must the word be inserted into the Trie AFTER calling canForm rather than before?

Back to DSA Sheet