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 <= 1041 <= words[i].length <= 30words[i]consists of only lowercase English letters.- All the strings of
wordsare unique. 1 <= sum(words[i].length) <= 105
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List findAllConcatenatedWordsInADict(String[] words) {
TrieNode root = new TrieNode('-');
for (String word : words) {
addWord(word, root);
}
List < String> concatenations = new ArrayList<>();
for (String word : words) {
if (isConcatentation(word, root, 0, 0)) {
concatenations.add(word);
}
}
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;
}
}
Input
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses"
Output
["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])
}
pre.add(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]
}
}
Input
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses"
Output
["catsdogcats","dogcatsdog","ratcatdogcat"]
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def findAllConcatenatedWordsInADict(self, words):
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,
w_set.add(w)
return res
Input
words = ["cat","dog","catdog"]
Output
["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))
result.Add(word);
set.Add(word);
}
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;
}
}
}
Input
words = ["cat","dog","catdog"]
Output
["catdog"]