Last updated on January 18th, 2025 at 09:47 pm

Here, we see a Concatenated Words LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Depth-First Search, Dynamic Programming, Tree

Level of Question

Hard

Concatenated Words LeetCode Solution

1. Problem Statement

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 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”]

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Dynamic Programming with Backtracking. This pattern is used to solve problems where the solution can be broken down into overlapping subproblems, and the results of these subproblems can be reused to optimize the solution. Specifically, the problem involves checking if a word can be formed by concatenating other words in the dictionary, which is a classic Word Break Problem.

3. Code Implementation in Different Languages

3.1 Concatenated Words C++

class Solution {
public:
    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        unordered_set<string> words_set;
        for (string word : words) words_set.insert(word);
        vector<string> res;
    
        for (string word : words) {
            int n = word.size();
            vector<int> dp(n + 1, 0);
            dp[0] = 1;
            for (int i = 0; i < n; i++) {
                if (!dp[i]) continue;
                for (int j = i + 1; j <= n; j++) {
                    if (j - i < n && words_set.count(word.substr(i, j - i))) {
                        dp[j] = 1;
                    }
                }
                if (dp[n]) {
                    res.push_back(word);
                    break;
                }
            }
        }
        return res;
    }
};

3.2 Concatenated Words Java

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<String> s = new HashSet<>();
        List<String> concatenateWords = new ArrayList<>();
        for(String word : words)
            s.add(word);
        for(String word : words) {
            if(checkConcatenate(word, s) == true)
                concatenateWords.add(word);
        }
        return concatenateWords;
    }
    public boolean checkConcatenate(String word, Set<String> s) {
        for(int i = 1; i < word.length(); i++) {
            String prefixWord = word.substring(0, i);
            String suffixWord = word.substring(i, word.length());
            if(s.contains(prefixWord) && (s.contains(suffixWord) || checkConcatenate(suffixWord, s)))
                return true;
        }
        return false;
    }
}

3.3 Concatenated Words JavaScript

var findAllConcatenatedWordsInADict = function(words) {
    const set = new Set(words);
    let res = []

    let isValid = (word) =>{
        if(word.length == 0) return true;
        for(let i =1; i<=word.length;i++){
            let value = word.slice(0,i);
            if(set.has(value)){
                let check = isValid(word.slice(i))
                if(check) return true;
            }
        }
        return false;
    }

    for(let word of words){
        set.delete(word);
        if(isValid(word)) res.push(word)
        set.add(word)
    }
    return res;
};

3.4 Concatenated Words Python

class Solution(object):
    def findAllConcatenatedWordsInADict(self, words):
        res = []
        preWords = set()
        words.sort(key = len)
        for word in words:
            if self.wordBreak(word, preWords):
                res.append(word)
            preWords.add(word)
        return res
    def wordBreak(self, string, words):
        if not words:
            return False
        dp = [False] * (len(string) + 1)
        dp[0] = True
        for i in range(len(string)+1):
            for j in range(i):
                if dp[j] and string[j:i] in words:
                    dp[i] = True
                    break
        
        return dp[-1]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(N * L²)	O(N * L)
Java	O(N * 2^L)	O(L)
JavaScript	O(N * 2^L)	O(L)
Python	O(N * L²)	O(N * L)

where,
N is the word.
L is the length of each word.