Course4all

Concatenated Words

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trie.

Concatenated Words

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words. A concatenated word is defined as a string that is entirely comprised of at least two shorter words in the given array.

Visual Representation

Words: ["cat", "dog", "catdog"] DFS(0): 1. Prefixes found: "cat" (Trie matches). 2. Remaining: "dog". 3. DFS("dog"): Prefix found: "dog". Remaining: "". 4. SUCCESS -> "catdog" is concatenated.
Hard

Examples

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Approach 1

Level I: Set-based DFS

Intuition

Use a HashSet to store all words. For each word, check if it can be partitioned into at least two shorter words present in the Set using a recursive DFS with memoization. Simple but less space-efficient for prefix matching.
⏱ O(N * L^2)💾 O(N * L)
java
import java.util.*;
class Solution {
    Set<String> dict;
    Map<String, Boolean> memo;
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        dict = new HashSet<>(Arrays.asList(words));
        List<String> res = new ArrayList<>();
        for (String word : words) {
            dict.remove(word); // Remove current word to avoid self-concatenation
            memo = new HashMap<>();
            if (canBreak(word)) res.add(word);
            dict.add(word); // Add it back for other words
        }
        return res;
    }
    private boolean canBreak(String s) {
        if (memo.containsKey(s)) return memo.get(s);
        if (dict.contains(s)) return true;
        for (int i = 1; i < s.length(); i++) {
            String prefix = s.substring(0, i);
            if (dict.contains(prefix) && canBreak(s.substring(i))) {
                memo.put(s, true); return true;
            }
        }
        memo.put(s, false); return false;
    }
}
Approach 2

Level III: Trie + DFS + Memoization

Intuition

First, sort the words by length. This allows us to only search for a word's composition using words that were previously added to the Trie (which are guaranteed to be shorter). For each word, use DFS with a Trie to check if it can be broken into multiple pieces that are already in the Trie.
⏱ O(N * L^2) where L is max length.💾 O(N * L) for Trie.
java
import java.util.*;
class Solution {
    class Node { Node[] children = new Node[26]; boolean isEnd = false; }
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        List<String> res = new ArrayList<>();
        Node root = new Node();
        for (String w : words) {
            if (canForm(w, 0, root, new Boolean[w.length()])) res.add(w);
            else insert(root, w);
        }
        return res;
    }
    private boolean canForm(String w, int start, Node root, Boolean[] memo) {
        if (start == w.length()) return true;
        if (memo[start] != null) return memo[start];
        Node curr = root;
        for (int i = start; i < w.length(); i++) {
            if (curr.children[w.charAt(i)-'a'] == null) break;
            curr = curr.children[w.charAt(i)-'a'];
            if (curr.isEnd && canForm(w, i + 1, root, memo)) return memo[start] = true;
        }
        return memo[start] = false;
    }
    private void insert(Node root, String w) {
        if (w.isEmpty()) return;
        Node curr = root;
        for (char c : w.toCharArray()) {
            if (curr.children[c-'a'] == null) curr.children[c-'a'] = new Node();
            curr = curr.children[c-'a'];
        }
        curr.isEnd = true;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionWord Ladder II
Next Question →Palindrome Pairs