472. Concatenated Words - Explanation

Description

You are given an array of strings words (without duplicates), return all the concatenated words in the given list of words in any order.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words (not necessarily distinct) in the given array.

Example 1:

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

Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]

Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

Example 2:

Input: words = ["cat","dog","catdog"]

Output: ["catdog"]

Constraints:

1 <= words.length <= 10,000
1 <= words[i].length <= 30
words[i] consists of only lowercase English letters.
All the strings of words are unique.
1 <= sum(words[i].length) <= 100,000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Hash Sets - Using sets for O(1) lookups to check if a word exists in the dictionary
Recursion - Breaking down strings into prefix/suffix and recursively checking validity
Dynamic Programming - Using memoization to avoid recomputing results for the same substrings
String Manipulation - Splitting strings into substrings and concatenating words

1. Brute Force (Backtracking)

Intuition

We can generate all possible concatenations of words and check if any concatenation exists in our word set. By building concatenations through backtracking and checking membership, we find words that are formed by joining two or more shorter words.

Algorithm

Build a hash set from all words and find the maximum word length.
Use backtracking to generate all possible concatenations of words.
When a concatenation has more than one word and exists in the word set, add it to results and remove it from the set to avoid duplicates.
Prune branches where the current length exceeds the maximum word length.
Return all found concatenated words.

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        n = len(words)
        res = []
        wordSet = set(words)
        maxLen = 0
        for w in words:
            maxLen = max(maxLen, len(w))

        def dfs(concatWord, totLen):
            if len(concatWord) > 1:
                word = "".join(concatWord)
                if word in wordSet:
                    res.append(word)
                    wordSet.remove(word)

            for i in range(len(words)):
                if totLen + len(words[i]) > maxLen:
                    continue
                concatWord.append(words[i])
                dfs(concatWord, totLen + len(words[i]))
                concatWord.pop()

        dfs([], 0)
        return res

public class Solution {
    private Set<String> wordSet;
    private int maxLen;
    private List<String> res;
    private String[] words;

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        this.words = words;
        this.wordSet = new HashSet<>(Arrays.asList(words));
        this.maxLen = 0;
        this.res = new ArrayList<>();

        for (String w : words) {
            maxLen = Math.max(maxLen, w.length());
        }

        dfs(new ArrayList<>(), 0);
        return res;
    }

    private void dfs(List<String> concatWord, int totLen) {
        if (concatWord.size() > 1) {
            String word = String.join("", concatWord);
            if (wordSet.contains(word)) {
                res.add(word);
                wordSet.remove(word);
            }
        }

        for (String word : words) {
            if (totLen + word.length() > maxLen) continue;
            concatWord.add(word);
            dfs(concatWord, totLen + word.length());
            concatWord.remove(concatWord.size() - 1);
        }
    }
}

class Solution {
private:
    unordered_set<string> wordSet;
    int maxLen;
    vector<string> res;
    vector<string> words;

public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        this->words = words;
        wordSet = unordered_set<string>(words.begin(), words.end());
        maxLen = 0;
        res.clear();

        for (const string& w : words) {
            maxLen = max(maxLen, (int)w.length());
        }

        vector<string> concatWord;
        dfs(concatWord, 0);
        return res;
    }

private:
    void dfs(vector<string>& concatWord, int totLen) {
        if (concatWord.size() > 1) {
            string word = accumulate(concatWord.begin(), concatWord.end(), string(""));
            if (wordSet.count(word)) {
                res.push_back(word);
                wordSet.erase(word);
            }
        }

        for (const string& word : words) {
            if (totLen + word.size() > maxLen) continue;
            concatWord.push_back(word);
            dfs(concatWord, totLen + word.length());
            concatWord.pop_back();
        }
    }
};

class Solution {
    /**
     * @param {string[]} words
     * @return {string[]}
     */
    findAllConcatenatedWordsInADict(words) {
        let n = words.length;
        let res = [];
        let wordSet = new Set(words);
        let maxLen = 0;

        for (let w of words) {
            maxLen = Math.max(maxLen, w.length);
        }

        const dfs = (concatWord, totLen) => {
            if (concatWord.length > 1) {
                let word = concatWord.join('');
                if (wordSet.has(word)) {
                    res.push(word);
                    wordSet.delete(word);
                }
            }

            for (let i = 0; i < words.length; i++) {
                if (totLen + words[i].length > maxLen) continue;
                concatWord.push(words[i]);
                dfs(concatWord, totLen + words[i].length);
                concatWord.pop();
            }
        };

        dfs([], 0);
        return res;
    }
}

public class Solution {
    private HashSet<string> wordSet;
    private int maxLen;
    private List<string> res;
    private string[] words;

    public List<string> FindAllConcatenatedWordsInADict(string[] words) {
        this.words = words;
        this.wordSet = new HashSet<string>(words);
        this.maxLen = 0;
        this.res = new List<string>();

        foreach (var w in words) {
            maxLen = Math.Max(maxLen, w.Length);
        }

        Dfs(new List<string>(), 0);
        return res;
    }

    private void Dfs(List<string> concatWord, int totLen) {
        if (concatWord.Count > 1) {
            string word = string.Concat(concatWord);
            if (wordSet.Contains(word)) {
                res.Add(word);
                wordSet.Remove(word);
            }
        }

        foreach (var word in words) {
            if (totLen + word.Length > maxLen) continue;
            concatWord.Add(word);
            Dfs(concatWord, totLen + word.Length);
            concatWord.RemoveAt(concatWord.Count - 1);
        }
    }
}

func findAllConcatenatedWordsInADict(words []string) []string {
    wordSet := make(map[string]bool)
    maxLen := 0
    for _, w := range words {
        wordSet[w] = true
        if len(w) > maxLen {
            maxLen = len(w)
        }
    }

    var res []string
    var dfs func(concatWord []string, totLen int)
    dfs = func(concatWord []string, totLen int) {
        if len(concatWord) > 1 {
            word := strings.Join(concatWord, "")
            if wordSet[word] {
                res = append(res, word)
                delete(wordSet, word)
            }
        }

        for _, w := range words {
            if totLen+len(w) > maxLen {
                continue
            }
            concatWord = append(concatWord, w)
            dfs(concatWord, totLen+len(w))
            concatWord = concatWord[:len(concatWord)-1]
        }
    }

    dfs([]string{}, 0)
    return res
}

class Solution {
    fun findAllConcatenatedWordsInADict(words: Array<String>): List<String> {
        val wordSet = words.toMutableSet()
        var maxLen = 0
        for (w in words) {
            maxLen = maxOf(maxLen, w.length)
        }

        val res = mutableListOf<String>()

        fun dfs(concatWord: MutableList<String>, totLen: Int) {
            if (concatWord.size > 1) {
                val word = concatWord.joinToString("")
                if (word in wordSet) {
                    res.add(word)
                    wordSet.remove(word)
                }
            }

            for (w in words) {
                if (totLen + w.length > maxLen) continue
                concatWord.add(w)
                dfs(concatWord, totLen + w.length)
                concatWord.removeAt(concatWord.size - 1)
            }
        }

        dfs(mutableListOf(), 0)
        return res
    }
}

class Solution {
    func findAllConcatenatedWordsInADict(_ words: [String]) -> [String] {
        var wordSet = Set(words)
        var maxLen = 0
        for w in words {
            maxLen = max(maxLen, w.count)
        }

        var res = [String]()

        func dfs(_ concatWord: inout [String], _ totLen: Int) {
            if concatWord.count > 1 {
                let word = concatWord.joined()
                if wordSet.contains(word) {
                    res.append(word)
                    wordSet.remove(word)
                }
            }

            for w in words {
                if totLen + w.count > maxLen { continue }
                concatWord.append(w)
                dfs(&concatWord, totLen + w.count)
                concatWord.removeLast()
            }
        }

        var concatWord = [String]()
        dfs(&concatWord, 0)
        return res
    }
}

impl Solution {
    pub fn find_all_concatenated_words_in_a_dict(words: Vec<String>) -> Vec<String> {
        let mut word_set: HashSet<String> = words.iter().cloned().collect();
        let max_len = words.iter().map(|w| w.len()).max().unwrap_or(0);
        let mut res = Vec::new();

        fn dfs(
            words: &[String], word_set: &mut HashSet<String>, max_len: usize,
            concat_word: &mut Vec<String>, tot_len: usize, res: &mut Vec<String>,
        ) {
            if concat_word.len() > 1 {
                let word: String = concat_word.concat();
                if word_set.contains(&word) {
                    res.push(word.clone());
                    word_set.remove(&word);
                }
            }
            for w in words {
                if tot_len + w.len() > max_len { continue; }
                concat_word.push(w.clone());
                dfs(words, word_set, max_len, concat_word, tot_len + w.len(), res);
                concat_word.pop();
            }
        }

        dfs(&words, &mut word_set, max_len, &mut vec![], 0, &mut res);
        res
    }
}

Time & Space Complexity

Time complexity: $O(m * n ^ n)$
Space complexity: $O(m * n)$

Where $n$ is the size of the string array $words$ and $m$ is the length of the longest word in the array.

2. Recursion

Intuition

For each word, we check if it can be split into parts where each part exists in the word set. We try every possible prefix; if a prefix is in the set, we recursively check if the remaining suffix can also be decomposed (or is itself in the set).

Algorithm

Build a hash set from all words for O(1) lookup.
For each word, define a recursive function that tries to split it.
At each position, check all possible prefixes. If a prefix exists in the set, check if the suffix also exists or can be recursively split.
If the entire word can be decomposed into at least two parts from the set, add it to results.
Return all concatenated words found.

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        wordSet = set(words)

        def dfs(word):
            for i in range(1, len(word)):
                prefix, suffix = word[:i], word[i:]
                if ((prefix in wordSet and suffix in wordSet) or
                    (prefix in wordSet and dfs(suffix))
                ):
                    return True
            return False

        res = []
        for w in words:
            if dfs(w):
                res.append(w)
        return res

public class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        List<String> res = new ArrayList<>();

        for (String w : words) {
            if (dfs(w, wordSet)) {
                res.add(w);
            }
        }
        return res;
    }

    private boolean dfs(String word, Set<String> wordSet) {
        for (int i = 1; i < word.length(); i++) {
            String prefix = word.substring(0, i);
            String suffix = word.substring(i);

            if ((wordSet.contains(prefix) && wordSet.contains(suffix)) ||
                (wordSet.contains(prefix) && dfs(suffix, wordSet))) {
                return true;
            }
        }
        return false;
    }
}

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_set<string> wordSet(words.begin(), words.end());
        vector<string> res;

        for (const string& w : words) {
            if (dfs(w, wordSet)) {
                res.push_back(w);
            }
        }
        return res;
    }

private:
    bool dfs(const string& word, unordered_set<string>& wordSet) {
        for (int i = 1; i < word.size(); i++) {
            string prefix = word.substr(0, i);
            string suffix = word.substr(i);

            if ((wordSet.count(prefix) && wordSet.count(suffix)) ||
                (wordSet.count(prefix) && dfs(suffix, wordSet))) {
                return true;
            }
        }
        return false;
    }
};

class Solution {
    /**
     * @param {string[]} words
     * @return {string[]}
     */
    findAllConcatenatedWordsInADict(words) {
        const wordSet = new Set(words);

        const dfs = (word) => {
            for (let i = 1; i < word.length; i++) {
                const prefix = word.substring(0, i);
                const suffix = word.substring(i);

                if (
                    (wordSet.has(prefix) && wordSet.has(suffix)) ||
                    (wordSet.has(prefix) && dfs(suffix))
                ) {
                    return true;
                }
            }
            return false;
        };

        const res = [];
        for (let w of words) {
            if (dfs(w)) {
                res.push(w);
            }
        }
        return res;
    }
}

public class Solution {
    private HashSet<string> wordSet;

    public List<string> FindAllConcatenatedWordsInADict(string[] words) {
        wordSet = new HashSet<string>(words);
        var res = new List<string>();
        foreach (var w in words) {
            if (Dfs(w)) {
                res.Add(w);
            }
        }
        return res;
    }

    private bool Dfs(string word) {
        for (int i = 1; i < word.Length; i++) {
            string prefix = word.Substring(0, i);
            string suffix = word.Substring(i);
            if ((wordSet.Contains(prefix) && wordSet.Contains(suffix)) ||
                (wordSet.Contains(prefix) && Dfs(suffix))) {
                return true;
            }
        }
        return false;
    }
}

func findAllConcatenatedWordsInADict(words []string) []string {
    wordSet := make(map[string]bool)
    for _, w := range words {
        wordSet[w] = true
    }

    var dfs func(word string) bool
    dfs = func(word string) bool {
        for i := 1; i < len(word); i++ {
            prefix, suffix := word[:i], word[i:]
            if (wordSet[prefix] && wordSet[suffix]) ||
                (wordSet[prefix] && dfs(suffix)) {
                return true
            }
        }
        return false
    }

    var res []string
    for _, w := range words {
        if dfs(w) {
            res = append(res, w)
        }
    }
    return res
}

class Solution {
    fun findAllConcatenatedWordsInADict(words: Array<String>): List<String> {
        val wordSet = words.toHashSet()

        fun dfs(word: String): Boolean {
            for (i in 1 until word.length) {
                val prefix = word.substring(0, i)
                val suffix = word.substring(i)
                if ((prefix in wordSet && suffix in wordSet) ||
                    (prefix in wordSet && dfs(suffix))) {
                    return true
                }
            }
            return false
        }

        val res = mutableListOf<String>()
        for (w in words) {
            if (dfs(w)) {
                res.add(w)
            }
        }
        return res
    }
}

class Solution {
    func findAllConcatenatedWordsInADict(_ words: [String]) -> [String] {
        let wordSet = Set(words)

        func dfs(_ word: String) -> Bool {
            for i in 1..<word.count {
                let prefixEnd = word.index(word.startIndex, offsetBy: i)
                let prefix = String(word[..<prefixEnd])
                let suffix = String(word[prefixEnd...])
                if (wordSet.contains(prefix) && wordSet.contains(suffix)) ||
                    (wordSet.contains(prefix) && dfs(suffix)) {
                    return true
                }
            }
            return false
        }

        var res = [String]()
        for w in words {
            if dfs(w) {
                res.append(w)
            }
        }
        return res
    }
}

impl Solution {
    pub fn find_all_concatenated_words_in_a_dict(words: Vec<String>) -> Vec<String> {
        let word_set: HashSet<&str> = words.iter().map(|s| s.as_str()).collect();

        fn dfs(word: &str, word_set: &HashSet<&str>) -> bool {
            for i in 1..word.len() {
                let prefix = &word[..i];
                let suffix = &word[i..];
                if (word_set.contains(prefix) && word_set.contains(suffix))
                    || (word_set.contains(prefix) && dfs(suffix, word_set))
                {
                    return true;
                }
            }
            false
        }

        words.iter()
            .filter(|w| dfs(w, &word_set))
            .cloned()
            .collect()
    }
}

Time & Space Complexity

Time complexity: $O(n * m ^ 4)$
Space complexity: $O(n * m)$

Where $n$ is the size of the string array $words$ and $m$ is the length of the longest word in the array.

3. Dynamic Programming (Top-Down)

Intuition

The recursive approach has overlapping subproblems since the same suffix may be checked multiple times. By memoizing results for each suffix, we avoid recomputing whether a substring can be decomposed.

Algorithm

Build a hash set from all words and create a memoization dictionary.
For each word, use a recursive function with memoization to check if it can be split.
Before computing, check if the result for the current word exists in memo.
Try all prefixes; if a prefix is in the word set and the suffix can be decomposed, cache and return true.
Cache false results as well to avoid recomputation. Add words that return true to the result.

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        wordSet = set(words)
        dp = {}

        def dfs(word):
            if word in dp:
                return dp[word]

            for i in range(1, len(word)):
                prefix, suffix = word[:i], word[i:]
                if ((prefix in wordSet and suffix in wordSet) or
                    (prefix in wordSet and dfs(suffix))
                ):
                    dp[word] = True
                    return True
            dp[word] = False
            return False

        res = []
        for w in words:
            if dfs(w):
                res.append(w)
        return res

public class Solution {
    private Map<String, Boolean> dp;

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        List<String> res = new ArrayList<>();
        dp = new HashMap<>();

        for (String w : words) {
            if (dfs(w, wordSet)) {
                res.add(w);
            }
        }
        return res;
    }

    private boolean dfs(String word, Set<String> wordSet) {
        if (dp.containsKey(word)) {
            return dp.get(word);
        }

        for (int i = 1; i < word.length(); i++) {
            String prefix = word.substring(0, i);
            String suffix = word.substring(i);

            if ((wordSet.contains(prefix) && wordSet.contains(suffix)) ||
                (wordSet.contains(prefix) && dfs(suffix, wordSet))) {
                dp.put(word, true);
                return true;
            }
        }
        dp.put(word, false);
        return false;
    }
}

class Solution {
    unordered_map<string, bool> dp;

public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_set<string> wordSet(words.begin(), words.end());
        vector<string> res;

        for (const string& w : words) {
            if (dfs(w, wordSet)) {
                res.push_back(w);
            }
        }
        return res;
    }

private:
    bool dfs(const string& word, unordered_set<string>& wordSet) {
        if (dp.count(word)) {
            return dp[word];
        }

        for (int i = 1; i < word.size(); i++) {
            string prefix = word.substr(0, i);
            string suffix = word.substr(i);

            if ((wordSet.count(prefix) && wordSet.count(suffix)) ||
                (wordSet.count(prefix) && dfs(suffix, wordSet))) {
                dp[word] = true;
                return true;
            }
        }
        dp[word] = false;
        return false;
    }
};

class Solution {
    /**
     * @param {string[]} words
     * @return {string[]}
     */
    findAllConcatenatedWordsInADict(words) {
        const wordSet = new Set(words);
        const dp = new Map();

        const dfs = (word) => {
            if (dp.has(word)) {
                return dp.get(word);
            }

            for (let i = 1; i < word.length; i++) {
                const prefix = word.substring(0, i);
                const suffix = word.substring(i);

                if (
                    (wordSet.has(prefix) && wordSet.has(suffix)) ||
                    (wordSet.has(prefix) && dfs(suffix))
                ) {
                    dp.set(word, true);
                    return true;
                }
            }
            dp.set(word, false);
            return false;
        };

        const res = [];
        for (let w of words) {
            if (dfs(w)) {
                res.push(w);
            }
        }
        return res;
    }
}

public class Solution {
    private HashSet<string> wordSet;
    private Dictionary<string, bool> dp;

    public List<string> FindAllConcatenatedWordsInADict(string[] words) {
        wordSet = new HashSet<string>(words);
        dp = new Dictionary<string, bool>();
        var res = new List<string>();
        foreach (var w in words) {
            if (Dfs(w)) {
                res.Add(w);
            }
        }
        return res;
    }

    private bool Dfs(string word) {
        if (dp.TryGetValue(word, out bool val)) {
            return val;
        }
        for (int i = 1; i < word.Length; i++) {
            string prefix = word.Substring(0, i);
            string suffix = word.Substring(i);
            if ((wordSet.Contains(prefix) && wordSet.Contains(suffix)) ||
                (wordSet.Contains(prefix) && Dfs(suffix))) {
                dp[word] = true;
                return true;
            }
        }
        dp[word] = false;
        return false;
    }
}

func findAllConcatenatedWordsInADict(words []string) []string {
    wordSet := make(map[string]bool)
    for _, w := range words {
        wordSet[w] = true
    }
    dp := make(map[string]bool)
    dpSet := make(map[string]bool)

    var dfs func(word string) bool
    dfs = func(word string) bool {
        if val, ok := dpSet[word]; ok {
            return val
        }

        for i := 1; i < len(word); i++ {
            prefix, suffix := word[:i], word[i:]
            if (wordSet[prefix] && wordSet[suffix]) ||
                (wordSet[prefix] && dfs(suffix)) {
                dp[word] = true
                dpSet[word] = true
                return true
            }
        }
        dp[word] = false
        dpSet[word] = true
        return false
    }

    var res []string
    for _, w := range words {
        if dfs(w) {
            res = append(res, w)
        }
    }
    return res
}

class Solution {
    fun findAllConcatenatedWordsInADict(words: Array<String>): List<String> {
        val wordSet = words.toHashSet()
        val dp = mutableMapOf<String, Boolean>()

        fun dfs(word: String): Boolean {
            if (word in dp) {
                return dp[word]!!
            }

            for (i in 1 until word.length) {
                val prefix = word.substring(0, i)
                val suffix = word.substring(i)
                if ((prefix in wordSet && suffix in wordSet) ||
                    (prefix in wordSet && dfs(suffix))) {
                    dp[word] = true
                    return true
                }
            }
            dp[word] = false
            return false
        }

        val res = mutableListOf<String>()
        for (w in words) {
            if (dfs(w)) {
                res.add(w)
            }
        }
        return res
    }
}

class Solution {
    func findAllConcatenatedWordsInADict(_ words: [String]) -> [String] {
        let wordSet = Set(words)
        var dp = [String: Bool]()

        func dfs(_ word: String) -> Bool {
            if let val = dp[word] {
                return val
            }

            for i in 1..<word.count {
                let prefixEnd = word.index(word.startIndex, offsetBy: i)
                let prefix = String(word[..<prefixEnd])
                let suffix = String(word[prefixEnd...])
                if (wordSet.contains(prefix) && wordSet.contains(suffix)) ||
                    (wordSet.contains(prefix) && dfs(suffix)) {
                    dp[word] = true
                    return true
                }
            }
            dp[word] = false
            return false
        }

        var res = [String]()
        for w in words {
            if dfs(w) {
                res.append(w)
            }
        }
        return res
    }
}

impl Solution {
    pub fn find_all_concatenated_words_in_a_dict(words: Vec<String>) -> Vec<String> {
        let word_set: HashSet<String> = words.iter().cloned().collect();
        let mut dp = HashMap::new();

        fn dfs(word: &str, word_set: &HashSet<String>, dp: &mut HashMap<String, bool>) -> bool {
            if let Some(&val) = dp.get(word) {
                return val;
            }
            for i in 1..word.len() {
                let prefix = &word[..i];
                let suffix = &word[i..];
                if (word_set.contains(prefix) && word_set.contains(suffix))
                    || (word_set.contains(prefix) && dfs(suffix, word_set, dp))
                {
                    dp.insert(word.to_string(), true);
                    return true;
                }
            }
            dp.insert(word.to_string(), false);
            false
        }

        words.iter()
            .filter(|w| dfs(w, &word_set, &mut dp))
            .cloned()
            .collect()
    }
}

Time & Space Complexity

Time complexity: $O(n * m ^ 3)$
Space complexity: $O(n * m)$

Where $n$ is the size of the string array $words$ and $m$ is the length of the longest word in the array.

4. Dynamic Programming (Bottom-Up)

Intuition

For each word, we use a DP array where dp[i] indicates whether the substring from index 0 to i can be formed by concatenating words from the set. We build this array iteratively by checking all possible split points.

Algorithm

Build a hash set from all words.
For each word, create a boolean DP array of size m+1 with dp[0] = true.
For each position i from 1 to m, check all previous positions j. If dp[j] is true and the substring from j to i exists in the set, set dp[i] = true.
Skip the case where j = 0 and i = m to ensure the word is not just itself.
If dp[m] is true, the word is concatenated; add it to results.

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        wordSet = set(words)
        res = []

        for word in words:
            m = len(word)

            dp = [False] * (m + 1)
            dp[0] = True

            for i in range(1, m + 1):
                for j in range(i):
                    if j == 0 and i == m:
                        continue
                    if dp[j] and word[j:i] in wordSet:
                        dp[i] = True
                        break

            if dp[m]:
                res.append(word)

        return res

public class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        List<String> res = new ArrayList<>();

        for (String word : words) {
            int m = word.length();
            boolean[] dp = new boolean[m + 1];
            dp[0] = true;

            for (int i = 1; i <= m; i++) {
                for (int j = 0; j < i; j++) {
                    if (j == 0 && i == m) continue;
                    if (dp[j] && wordSet.contains(word.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }

            if (dp[m]) {
                res.add(word);
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_set<string> wordSet(words.begin(), words.end());
        vector<string> res;

        for (string& word : words) {
            int m = word.length();
            vector<bool> dp(m + 1, false);
            dp[0] = true;

            for (int i = 1; i <= m; i++) {
                for (int j = 0; j < i; j++) {
                    if (j == 0 && i == m) continue;
                    if (dp[j] && wordSet.count(word.substr(j, i - j))) {
                        dp[i] = true;
                        break;
                    }
                }
            }

            if (dp[m]) {
                res.push_back(word);
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string[]} words
     * @return {string[]}
     */
    findAllConcatenatedWordsInADict(words) {
        const wordSet = new Set(words);
        const res = [];

        for (const word of words) {
            const m = word.length;
            const dp = new Array(m + 1).fill(false);
            dp[0] = true;

            for (let i = 1; i <= m; i++) {
                for (let j = 0; j < i; j++) {
                    if (j === 0 && i === m) continue;
                    if (dp[j] && wordSet.has(word.substring(j, i))) {
                        dp[i] = true;
                        break;
                    }
                }
            }

            if (dp[m]) {
                res.push(word);
            }
        }
        return res;
    }
}

public class Solution {
    public List<string> FindAllConcatenatedWordsInADict(string[] words) {
        var wordSet = new HashSet<string>(words);
        var res = new List<string>();

        foreach (var word in words) {
            int m = word.Length;
            var dp = new bool[m + 1];
            dp[0] = true;

            for (int i = 1; i <= m; i++) {
                for (int j = 0; j < i; j++) {
                    if (j == 0 && i == m) continue;
                    if (dp[j] && wordSet.Contains(word.Substring(j, i - j))) {
                        dp[i] = true;
                        break;
                    }
                }
            }

            if (dp[m]) {
                res.Add(word);
            }
        }

        return res;
    }
}

func findAllConcatenatedWordsInADict(words []string) []string {
    wordSet := make(map[string]bool)
    for _, w := range words {
        wordSet[w] = true
    }

    var res []string
    for _, word := range words {
        m := len(word)
        dp := make([]bool, m+1)
        dp[0] = true

        for i := 1; i <= m; i++ {
            for j := 0; j < i; j++ {
                if j == 0 && i == m {
                    continue
                }
                if dp[j] && wordSet[word[j:i]] {
                    dp[i] = true
                    break
                }
            }
        }

        if dp[m] {
            res = append(res, word)
        }
    }
    return res
}

class Solution {
    fun findAllConcatenatedWordsInADict(words: Array<String>): List<String> {
        val wordSet = words.toHashSet()
        val res = mutableListOf<String>()

        for (word in words) {
            val m = word.length
            val dp = BooleanArray(m + 1)
            dp[0] = true

            for (i in 1..m) {
                for (j in 0 until i) {
                    if (j == 0 && i == m) continue
                    if (dp[j] && word.substring(j, i) in wordSet) {
                        dp[i] = true
                        break
                    }
                }
            }

            if (dp[m]) {
                res.add(word)
            }
        }
        return res
    }
}

class Solution {
    func findAllConcatenatedWordsInADict(_ words: [String]) -> [String] {
        let wordSet = Set(words)
        var res = [String]()

        for word in words {
            let m = word.count
            var dp = [Bool](repeating: false, count: m + 1)
            dp[0] = true
            let chars = Array(word)

            for i in 1...m {
                for j in 0..<i {
                    if j == 0 && i == m { continue }
                    if dp[j] && wordSet.contains(String(chars[j..<i])) {
                        dp[i] = true
                        break
                    }
                }
            }

            if dp[m] {
                res.append(word)
            }
        }
        return res
    }
}

impl Solution {
    pub fn find_all_concatenated_words_in_a_dict(words: Vec<String>) -> Vec<String> {
        let word_set: HashSet<&str> = words.iter().map(|s| s.as_str()).collect();
        let mut res = Vec::new();

        for word in &words {
            let m = word.len();
            let mut dp = vec![false; m + 1];
            dp[0] = true;

            for i in 1..=m {
                for j in 0..i {
                    if j == 0 && i == m { continue; }
                    if dp[j] && word_set.contains(&word[j..i]) {
                        dp[i] = true;
                        break;
                    }
                }
            }

            if dp[m] {
                res.push(word.clone());
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n * m ^ 3)$
Space complexity: $O(n * m)$

Where $n$ is the size of the string array $words$ and $m$ is the length of the longest word in the array.

Common Pitfalls

Counting a Word as Its Own Concatenation

A concatenated word must be formed by at least two other words. If you check whether the entire word exists in the set without excluding it, every word would trivially match itself.

# Wrong: allows word to match itself
if word[j:i] in wordSet:
    dp[i] = True

# Correct: skip the case where the entire word is checked
if j == 0 and i == m:
    continue

Not Requiring Multiple Words

The problem requires concatenation of two or more words. Checking only that the word can be split into valid parts without ensuring at least two parts will incorrectly include single words that exist in the dictionary.

Missing Memoization Leading to TLE

Without memoization, the same suffix may be checked exponentially many times. For long words with many valid prefixes, this causes timeout.

# Wrong: no caching
def dfs(word):
    for i in range(1, len(word)):
        if prefix in wordSet and dfs(suffix):
            return True

# Correct: cache results
if word in dp:
    return dp[word]

Incorrect Substring Indices

Off-by-one errors when splitting the word into prefix and suffix are common. The prefix should be word[0:i] and suffix should be word[i:], where i ranges from 1 to len(word)-1.

Forgetting Empty String Edge Case

If the word list contains an empty string, it could match infinitely. Most solutions implicitly handle this since the loop starts at i=1, but explicitly filtering empty strings from the word set is safer.