Concatenated Words — Solution in Python, Java & C++
Concatenated Words solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Concatenated Words is a hard coding problem on strings, dynamic programming and depth-first search, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Strings, Dynamic Programming, Depth-First Search, Trie
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an array of distinct strings words. A concatenated word is a word of the array that can be written as the concatenation of at least two words of the array (the same word may be used more than once, but a word does not count as a concatenation of itself alone).
Return all concatenated words, in the order they appear in words.
Example 1
Input: words = ["code","kai","ro","kairo","codekairo","rocode","dsa"]
Output: ["kairo","codekairo","rocode"]
Explanation: `kairo` = `kai` + `ro`, `codekairo` = `code` + `kairo` (or `code` + `kai` + `ro`), `rocode` = `ro` + `code`.
Example 2
Input: words = ["a","b","ab","abc"]
Output: ["ab"]
Example 3
Input: words = ["x"]
Output: []
Constraints
1 <= words.length <= 10^41 <= words[i].length <= 30words[i] consists of only lowercase English lettersAll the strings of words are unique1 <= sum(words[i].length) <= 10^5
Hints for Concatenated Words
Hint 1
For a single word this is Word Break: can the word be cut into pieces that are all in the dictionary?
Hint 2
Use
ok[i]= "the firstiletters can be cut into dictionary words", withok[0] = trueandok[i] = ok[j] && word[j..i) in dictfor somej < i.Hint 3
The only twist is "at least two pieces": when computing
ok[len], do not allow the single pieceword[0..len)(that is the word itself).
How to solve Concatenated Words
Run the Word Break dynamic programme on every word against a hash set of all words, forbidding the one split that uses the whole word as a single piece.
Approach
- Put every word into a hash set.
- For each word
wof lengthL: setok[0] = true; fori = 1..L, setok[i] = trueif somej < ihasok[j]andw[j..i)in the set — but wheni == L, requirej >= 1. - If
ok[L]is true,wis a concatenated word; append it to the answer (this keeps input order).
Why it works
ok[i] is true exactly when the prefix of length i splits into dictionary words, by induction on i (the last piece w[j..i) plus a valid split of the first j letters). Requiring j >= 1 at i == L rules out precisely the one-piece split, so ok[L] means at least two pieces.
Complexity
- Time —
O(Σ L^2) hash lookups (each of a substring of length up to 30) - Space —
O(total length)
Pitfalls
- Without the
j >= 1rule every word trivially matches itself. - Removing the current word from the set while checking it also works, but forgetting to put it back breaks later words.
- A plain recursive search without memoisation can explode on words like
aaaaaaaa…b.
Reference solution
Python
from typing import List
def findAllConcatenatedWordsInADict(words: List[str]) -> List[str]:
dictionary = set(words)
res = []
for w in words:
n = len(w)
ok = [False] * (n + 1)
ok[0] = True
for i in range(1, n + 1):
for j in range(0 if i < n else 1, i):
if ok[j] and w[j:i] in dictionary:
ok[i] = True
break
if ok[n]:
res.append(w)
return resJava
public static String[] findAllConcatenatedWordsInADict(String[] words) {
Set<String> dict = new HashSet<>(Arrays.asList(words));
List<String> res = new ArrayList<>();
for (String w : words) {
int n = w.length();
boolean[] ok = new boolean[n + 1];
ok[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i < n ? 0 : 1; j < i; j++) {
if (ok[j] && dict.contains(w.substring(j, i))) {
ok[i] = true;
break;
}
}
}
if (ok[n]) res.add(w);
}
return res.toArray(new String[0]);
}C++
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
unordered_set<string> dict(words.begin(), words.end());
vector<string> res;
for (const string& w : words) {
int n = w.size();
vector<bool> ok(n + 1, false);
ok[0] = true;
for (int i = 1; i <= n; i++) {
for (int j = i < n ? 0 : 1; j < i; j++) {
if (ok[j] && dict.count(w.substr(j, i - j))) {
ok[i] = true;
break;
}
}
}
if (ok[n]) res.push_back(w);
}
return res;
}JavaScript
var findAllConcatenatedWordsInADict = function(words) {
var dict = new Set(words);
var res = [];
for (var k = 0; k < words.length; k++) {
var w = words[k], n = w.length;
var ok = new Array(n + 1).fill(false);
ok[0] = true;
for (var i = 1; i <= n; i++) {
for (var j = i < n ? 0 : 1; j < i; j++) {
if (ok[j] && dict.has(w.substring(j, i))) {
ok[i] = true;
break;
}
}
}
if (ok[n]) res.push(w);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming