Course4all
Join us on telegram
Home/dsa/Trie/Concatenated Words

Concatenated Words

Master this topic with zero to advance depth.

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;
    }
}
← Previous QuestionWord Ladder II
Next Question →Palindrome Pairs