Concatenated Words

Hard
1268.

Concatenated Words

Concatenated Words is a hard coding problem on strings, dynamic programming and depth-first search, asked in Amazon, Google and Meta interviews.

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^4
  • 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) <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} words
 * @return {string[]}
 */
var findAllConcatenatedWordsInADict = function(words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^4
  • 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) <= 10^5

Hints for Concatenated Words

  1. Hint 1

    For a single word this is Word Break: can the word be cut into pieces that are all in the dictionary?

  2. Hint 2

    Use ok[i] = "the first i letters can be cut into dictionary words", with ok[0] = true and ok[i] = ok[j] && word[j..i) in dict for some j < i.

  3. Hint 3

    The only twist is "at least two pieces": when computing ok[len], do not allow the single piece word[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

  1. Put every word into a hash set.
  2. For each word w of length L: set ok[0] = true; for i = 1..L, set ok[i] = true if some j < i has ok[j] and w[j..i) in the set — but when i == L, require j >= 1.
  3. If ok[L] is true, w is 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 >= 1 rule 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 res

Java

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