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](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Concatenated Words LeetCode Solution
Table of Contents
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”]
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;
}
};
Code language: PHP (php)
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;
}
}
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)
set.add(word)
}
return res;
};
Code language: JavaScript (javascript)
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]