Concatenated Words — Trie + Word Break DP

Problem Statement#

LeetCode 472 — Concatenated Words | Difficulty: Hard

Given an array of strings words (no duplicates), return all the concatenated words in words.

A concatenated word is a string that is comprised entirely of at least two shorter words from the same array.

Example:

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"

Constraints:

• 1 <= words.length <= 10^4
• 1 <= words[i].length <= 30
• 0 <= sum(words[i].length) <= 10^5
• Lowercase English letters only.

Why This Problem Matters#

Concatenated Words is the canonical "trie meets DP" hard interview problem, asked at Amazon (it appears verbatim in their OA pool), Google, Microsoft, and ByteDance. It tests whether a candidate can compose two algorithmic primitives — the prefix tree for fast dictionary membership and Word Break DP for segment partitioning — into a single elegant solution.

The pattern shows up in production code for tokenisers, search-query rewrite engines, hashtag splitters (the famous "Genuinely a programming legend" ambiguity), and DNA sequence matching. Understanding why brute recursion is exponential and why trie-guided DP is polynomial is exactly the skill interviewers probe.

The Core Insight#

Two ideas compose:

1. Word Break DP — define dp[i] = True if word[0:i] can be segmented into dictionary entries. Transition: dp[i] = True if there exists j < i such that dp[j] is True and word[j:i] is in the dictionary. Final answer requires dp[L] plus at least two segments used.
2. Trie acceleration — the inner word[j:i] in dictionary check, naively O(L), becomes O(1) per character if we walk a trie of all dictionary words. We start at trie root for index j and step character by character; whenever we reach a terminal node, we have a valid segment ending at the current position.

Combining them: for each candidate word, scan from each starting index, walk the trie, mark dp[i] = True whenever we land on a terminal node and dp[start] is already True. The answer is dp[L] provided we used at least two segments.

A clean shortcut: skip any word equal to itself in the dictionary (j > 0 or i < n guard). That enforces "at least two shorter words" without explicit count-tracking.

Visual Dry Run#

Dictionary ["cat", "cats", "dog", "rat"]. Test word "catsdog":

Trie of dictionary:

root
 |-- c -- a -- t (END "cat")
 |              |-- s (END "cats")
 |
 |-- d -- o -- g (END "dog")
 |
 |-- r -- a -- t (END "rat")

DP table for "catsdog" (length 7):

indices: 0 1 2 3 4 5 6 7
chars:   c a t s d o g
dp:      T F F T T F F T

Walk:

• dp[0] = True (empty prefix).
• From index 0 walk trie c→a→t (terminal at depth 3) → set dp[3] = True. Continue c→a→t→s (terminal at depth 4) → set dp[4] = True.
• From index 4 (where dp is True) walk trie d→o→g (terminal at depth 7 from start) → set dp[7] = True.
• dp[7] = True and we used segments "cats" + "dog" (two distinct words, neither equal to original) → "catsdog" is concatenated.

Solution (Optimal) — Trie + Word Break DP#

Python#

class TrieNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Solution:
    def findAllConcatenatedWordsInADict(self, words: list[str]) -> list[str]:
        root = TrieNode()
        # Build trie of dictionary
        for w in words:
            if not w: continue
            node = root
            for ch in w:
                node = node.children.setdefault(ch, TrieNode())
            node.is_end = True
 
        def can_form(w: str) -> bool:
            n = len(w)
            if n == 0: return False
            dp = [False] * (n + 1)
            dp[0] = True
            for i in range(n):
                if not dp[i]: continue
                node = root
                for j in range(i, n):
                    ch = w[j]
                    if ch not in node.children: break
                    node = node.children[ch]
                    if node.is_end:
                        # Found a dictionary word w[i:j+1].
                        # Skip the case where it spans the entire input (would not be "shorter").
                        if i == 0 and j + 1 == n:
                            continue
                        dp[j + 1] = True
            return dp[n]
 
        return [w for w in words if can_form(w)]

JavaScript#

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}
 
var findAllConcatenatedWordsInADict = function(words) {
  const root = new TrieNode();
  for (const w of words) {
    if (!w) continue;
    let node = root;
    for (const ch of w) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
  }
  const canForm = (w) => {
    const n = w.length;
    if (n === 0) return false;
    const dp = new Array(n + 1).fill(false);
    dp[0] = true;
    for (let i = 0; i < n; i++) {
      if (!dp[i]) continue;
      let node = root;
      for (let j = i; j < n; j++) {
        const ch = w[j];
        if (!node.children[ch]) break;
        node = node.children[ch];
        if (node.isEnd) {
          if (i === 0 && j + 1 === n) continue;
          dp[j + 1] = true;
        }
      }
    }
    return dp[n];
  };
  return words.filter(canForm);
};

Complexity#

• Time: O(N times L^2) — for each of N words, the DP visits each start index and each end index, each step performing O(1) trie traversal.
• Space: O(sum of L) for trie + O(L) for dp per word.

Common Mistakes#

1. Calling Word Break recursively without memoisation — exponential on adversarial inputs like "aaaaaab" with dictionary ["a","aa","aaa","..."].
2. Forgetting the at-least-two-words constraint — return True for words that match dictionary entries themselves. The i == 0 and j + 1 == n skip handles this exactly.
3. Including empty string in the dictionary — causes infinite loops; filter empties before building the trie.
4. Re-creating the trie per word — the trie should be built once across all words and reused for every can_form check.
5. Using set lookup with word[j:i] in word_set — works but creates O(L) substring per check, total O(N times L^3) and slower.
6. Skipping the dp[0] = True initialisation — DP never fires; output stays empty.

Interview Tips#

• Start with brute recursion, then add memoisation, then introduce the trie. Building up shows depth.
• Justify the trie: "Word break DP makes O(L^2) substring lookups per word; with set this is O(L^3) per word, with trie this is O(L^2)."
• Mention the at-least-two-words guard explicitly — it is the most common bug.
• For very long inputs (sum-of-lengths up to 10^5), highlight that the trie + DP is optimal; a pure DFS with memoisation is borderline.
• If the interviewer asks "what if the dictionary is huge but words are short?", note that the trie-build is amortised over many queries.

Follow-up Questions#

• What if words can be reused? Same algorithm; the dp does not track usage.
• Return one such concatenation, not just yes/no? Track parent pointers in dp; reconstruct backwards.
• Count number of distinct concatenations? Replace dp[i] = True/False with dp[i] = number of ways; sum over all decompositions.
• Streaming dictionary? Trie supports incremental inserts; can_form remains O(L^2).
• Memory pressure on dictionaries with millions of words? Compress with double-array trie or DAWG.

Key Takeaways#

• Concatenated Words = Word Break DP guided by a trie of the dictionary.
• Trie reduces the "is word[j:i] in dict" check from O(L) string-key lookup to O(1) per character traversal.
• Total complexity O(N times L^2) is provably optimal for this constraint set.
• The i == 0 and j+1 == n guard enforces "at least two shorter words" elegantly.
• Build the trie once across all words; reuse for every can_form query.
• This pattern (trie-guided DP) appears in autocorrect, search query rewriting, and tokenisation in production NLP systems.