Last updated on October 9th, 2024 at 06:12 pm

Here, We see Concatenated Words LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Concatenated Words LeetCode Solution

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

1. Concatenated Words LeetCode Solution 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;
    }
};

2. Concatenated Words LeetCode Solution 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. Concatenated Words Solution 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;
};

4. Concatenated Words Solution 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]