Concatenated Words - Video Solutions

Problem Overview: You are given a dictionary of unique words. The task is to return all words that can be formed by concatenating at least two shorter words from the same dictionary. Each word can reuse other dictionary entries, but the concatenated word itself cannot be counted as its own component.

Approach 1: Trie + Depth-First Search (O(N * L^2) time, O(N * L) space)

This approach stores all words in a trie and checks each word using depth-first search. Starting from index 0, traverse the trie character by character. Whenever you reach a terminal node (a complete word), recursively attempt to match the remaining suffix. If the DFS reaches the end of the string after using at least two words, the word is valid. The trie allows fast prefix checks while DFS explores possible split points. This method works well when many words share prefixes because trie traversal avoids repeated substring lookups.

The key idea is treating the word as a sequence of smaller dictionary prefixes. The trie ensures prefix lookups happen in O(L) time, while DFS handles branching splits. Memoization on indices can further reduce repeated work when the same suffix is evaluated multiple times.

Approach 2: Dynamic Programming (O(N * L^2) time, O(L) space per word)

This solution treats the problem like a classic word break variant using dynamic programming. Sort words by length so shorter words are processed first. For each word, build a boolean DP array where dp[i] indicates whether the prefix ending at index i can be formed using previously processed words. Iterate over all split points j < i and check if dp[j] is true and the substring word[j:i] exists in a hash set.

If the final index becomes reachable and the word uses at least two components, it is a concatenated word. After evaluation, add the word to the dictionary so longer words can reuse it. Sorting ensures each word only depends on smaller ones, preventing self-construction. This approach is straightforward and relies heavily on efficient substring membership checks.

Recommended for interviews: The dynamic programming approach is usually expected because it mirrors the classic Word Break pattern and is easier to reason about during an interview. Implementing trie + DFS demonstrates stronger understanding of prefix structures and search strategies, which can be useful when the dictionary has heavy prefix overlap. Showing the DP baseline first and then discussing trie optimization demonstrates strong problem-solving depth.