Concatenated Words

Concatenated Words layers two classic ideas: word-break dynamic programming and a smart ordering trick. A word counts if it is built entirely out of other, shorter words in the list — so the order you process words in is what makes the whole thing click.

The slow way first

The brute-force idea: for every word, try every possible way to chop it into pieces and check whether each piece is in the list. The number of ways to split a word of length m is exponential, so this blows up fast.

The question to ask: when I test a word, which other words am I allowed to use? Only shorter ones — a word can never be part of itself. So if I process words shortest first, every word I might need is already known by the time I get there.

The idea: sort by length, then word-break

Sort the words so shorter words come first. Keep a growing set seen of words processed so far. For each new word, run word-break DP against seen:

• dp[k] means "the first k characters can be split into seen-words."
• dp[0] = True (the empty prefix is trivially buildable).
• dp[j] is True if some earlier split point i has dp[i] True and the chunk word[i:j] is in seen.

If dp[len(word)] ends up True, the whole word was built from shorter words — it is concatenated. Then add the word to seen so even longer words can use it.

Sorting is what guarantees correctness: a longer word can only be built from words that are strictly shorter, and those are exactly the ones already in seen.

Walk through it

Step through the animation. "cat" and "dog" come first; seen is empty or too small to build them, so they are base words and just get added. When "catdog" arrives, the DP finds a valid split after "cat" (dp[3] becomes True) and then after "dog" (dp[6] becomes True), reaching the end — so "catdog" is concatenated.

Pseudocode

sort words by length (shortest first)
seen = empty set, result = empty list
for each word:
    dp = array of False of length len(word)+1
    dp[0] = True
    for j from 1 to len(word):
        for i from 0 to j-1:
            if dp[i] and word[i:j] is in seen:
                dp[j] = True
    if dp[len(word)] is True and word is non-empty:
        add word to result
    add word to seen          # available to longer words later
return result

The Python solution

def concatenated(words):
    words.sort(key=len)
    seen, result = set(), []
    for word in words:
        dp = [False] * (len(word) + 1)
        dp[0] = True
        for j in range(1, len(word) + 1):
            for i in range(j):
                if dp[i] and word[i:j] in seen:
                    dp[j] = True
        if dp[len(word)] and word:
            result.append(word)
        seen.add(word)
    return result

• words.sort(key=len) puts shorter words first, so seen always holds every word we are allowed to use.
• dp[k] is True when the first k characters split cleanly into seen-words; dp[0] = True seeds it.
• The double loop tries every split point: for each end j, look for a start i where the left part is already buildable (dp[i]) and the chunk word[i:j] is a known word.
• dp[len(word)] and word is the success check — the empty string is excluded so it is never falsely "concatenated."
• seen.add(word) happens after the check, so a word is never matched against itself.

Complexity

The seen set holds up to n words and each DP array is O(m), giving O(n · m) extra space. The quadratic word-break is the same DP that powers the classic "Word Break" problem.

When this pattern shows up

Practice