## Algorithm

Problem Name: 472. Concatenated Words

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 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 <= 104
• 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) <= 105

## Code Examples

### #1 Code Example with Java Programming

Code - Java Programming

class Solution {
TrieNode root = new TrieNode('-');
for (String word : words) {
}
List < String> concatenations = new ArrayList<>();
for (String word : words) {
if (isConcatentation(word, root, 0, 0)) {
}
}
return concatenations;
}

private void addWord(String s, TrieNode root) {
TrieNode curr = root;
for (int i = 0; i  <  s.length(); i++) {
if (!curr.map.containsKey(s.charAt(i))) {
curr.map.put(s.charAt(i), new TrieNode(s.charAt(i)));
}
curr = curr.map.get(s.charAt(i));
}
curr.isWord = true;
}

private boolean isConcatentation(String s, TrieNode root, int idx, int count) {
TrieNode curr = root;
for (int i = idx; i  <  s.length(); i++) {
if (!curr.map.containsKey(s.charAt(i))) {
return false;
}
if (curr.map.get(s.charAt(i)).isWord) {
if (i == s.length() - 1) {
return count >= 1;
}
if (isConcatentation(s, root, i + 1, count + 1)) {
return true;
}
}
curr = curr.map.get(s.charAt(i));
}
return false;
}
}

class TrieNode {
char c;
Map < Character, TrieNode> map;
boolean isWord;

public TrieNode(char c) {
this.c = c;
map = new HashMap < >();
isWord = false;
}
}
Copy The Code &

Input

cmd
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses"

Output

cmd
["catsdogcats","dogcatsdog","ratcatdogcat"]

### #2 Code Example with Javascript Programming

Code - Javascript Programming

const findAllConcatenatedWordsInADict = function (words) {
const pre = new Set()
words.sort((a, b) => a.length - b.length)
const res = []
for(let i = 0; i  <  words.length; i++) {
if(valid(words[i], pre)) {
res.push(words[i])
}
}

return res

function valid(str, set) {
if(set.size === 0) return false
const dp = Array(str.length + 1).fill(false)
dp[0] = true
for(let i = 1; i <= str.length; i++) {
for(let j = 0; j  <  i; j++) {
if(!dp[j]) continue
if(set.has(str.slice(j, i))> {
dp[i] = true
break
}
}
}

return dp[str.length]
}
}
Copy The Code &

Input

cmd
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses"

Output

cmd
["catsdogcats","dogcatsdog","ratcatdogcat"]

### #3 Code Example with Python Programming

Code - Python Programming

class Solution:
def check(w, st):
if w in st: return True
for i in range(1, len(w)):
if w[:i] in st and check(w[i:], st): return True
return False
w_set, res = set(words), []
for w in words:
w_set.remove(w)
if check(w, w_set): res += w,
return res
Copy The Code &

Input

cmd
words = ["cat","dog","catdog"]

Output

cmd
["catdog"]

### #4 Code Example with C# Programming

Code - C# Programming

using System.Collections.Generic;

namespace LeetCode
{
public class _0472_ConcatenatedWords
{
public IList < string> FindAllConcatenatedWordsInADict(string[] words)
{
var set = new HashSet(words);
var result = new List();

foreach (var word in words)
{
set.Remove(word);
if (DFS(word, set))
}

return result;
}

private bool DFS(string word, HashSet < string> set)
{
if (set.Contains(word)) return true;

for (int i = word.Length - 1; i > 0; i--)
{
var str = word.Substring(0, i);
if (set.Contains(str) && DFS(word.Substring(i), set)) return true;
}
return false;
}
}
}
Copy The Code &

Input

cmd
words = ["cat","dog","catdog"]

Output

cmd
["catdog"]