# Concatenated Words LeetCode Solution

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

## Problem Statement

Given an array of strings `words` (without duplicates), return all the concatenated words in the given list of `words`.

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

## Concatenated Words LeetCode Solution C++

``````class Solution {
public:
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;
}
};```Code language: PHP (php)```

## Concatenated Words LeetCode Solution Java

``````class Solution {
Set<String> s = new HashSet<>();
List<String> concatenateWords = new ArrayList<>();
for(String word : words)
for(String word : words) {
if(checkConcatenate(word, s) == true)
}
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;
}
}```Code language: JavaScript (javascript)```

## 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)
}
return res;
};```Code language: JavaScript (javascript)```

## Concatenated Words Solution Python

``````class Solution(object):
res = []
preWords = set()
words.sort(key = len)
for word in words:
if self.wordBreak(word, preWords):
res.append(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]``````
Scroll to Top