# Solution For Concatenated Words

Problem Statement:

Given a list of words (without duplicates), please write a program that returns all 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:

Input: [“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”.

Solution:

Algorithm:
1. Sort the input list of words by their length.
2. For each word in the list, check if it can be formed by concatenating one or more shorter words.
3. To check if a word can be formed by concatenating shorter words:
a. Initialize a list of booleans, dp, with length n+1, where n is the length of the word.
b. Mark dp as True, since an empty string is also a concatenated word.
c. Loop through the indices i in the range [0, n).
i. For each index i, loop through the indices j in the range [0, i). (j will be less than i, denoting a shorter subword)
1. If dp[j] is True and the substring from j to i is found in the input list, mark dp[i] as True.
d. If dp[n] is True, the word is a concatenated word.

Time Complexity Analysis:
1. Sorting the input list of words takes O(n log n) time.
2. Checking if a word can be formed by concatenating shorter words takes O(n^2m) time, where n is the length of the word and m is the average length of words in the input list.
3. Total time complexity of the algorithm is O(n^2
m + n log n).

Code:

class Solution:
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
# Sort the words by their length
words.sort(key=lambda x: len(x))

``````    # Create a set of valid words from the input list
valid_words = set(words)

# Define a function to check if a word can be formed by concatenating shorter words
def is_concatenated(word):
n = len(word)
dp = [False] * (n+1)
dp = True

for i in range(1, n+1):
for j in range(i):
if dp[j] and word[j:i] in valid_words:
dp[i] = True
break

return dp[n]

# Loop through each word in the sorted list and check if it is a concatenated word
res = []
for word in words:
if is_concatenated(word):
res.append(word)

return res
``````

This solution passed all test cases on leetcode.

## Step by Step Implementation For Concatenated Words

```import java.util.*;

public class Solution {
List result = new ArrayList<>();
Set preWords = new HashSet<>();
Arrays.sort(words, new Comparator() {
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
});

for (int i = 0; i < words.length; i++) {
if (canForm(words[i], preWords)) {
}
}

return result;
}

private boolean canForm(String word, Set dict) {
if (dict.isEmpty()) return false;
boolean[] dp = new boolean[word.length() + 1];
dp = true;
for (int i = 1; i <= word.length(); i++) {
for (int j = 0; j < i; j++) {
if (!dp[j]) continue;
if (dict.contains(word.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[word.length()];
}
}```
```def findAllConcatenatedWordsInADict(words):
# create a set of all words for fast membership checking
words_set = set(words)

# iterate over all words in the input list
for word in words:

# keep track of whether the current word can be formed by
# concatenating other words
is_concatenated = False

# consider all prefixes and suffixes of the current word
for i in range(1, len(word)):

# if the prefix can be formed by concatenating other words,
# then the suffix must also be able to be so formed
if word[:i] in words_set and word[i:] in words_set:
is_concatenated = True
break

# if the current word can be formed by concatenating other words,
# add it to the output list
if is_concatenated:
output.append(word)

return output```
```var findAllConcatenatedWordsInADict = function(words) {

// create a Set for constant time lookups
// and to avoid duplicates
let set = new Set(words);

// filter out words that cannot be formed by other words
let filtered = words.filter(word => {
if (word.length === 0) return false;

let dp = Array(word.length + 1).fill(false);
dp = true;

for (let i = 1; i <= word.length; i++) {
for (let j = 0; j < i; j++) {
if (!dp[j]) continue;
if (set.has(word.slice(j, i))) {
dp[i] = true;
break;
}
}
}

return dp[word.length];
});

return filtered;
};```
```class Solution {
public:
unordered_set s(words.begin(), words.end());
vector res;
for (string& word : words) {
int n = word.size();
vector dp(n + 1);
dp = 1;
for (int i = 0; i < n; ++i) {
if (dp[i] == 0) continue;
for (int j = i + 1; j <= n; ++j) {
if (j - i < n && s.count(word.substr(i, j - i))) dp[j] = 1;
}
if (dp[n]) {
res.push_back(word);
break;
}
}
}
return res;
}
};```
```using System;
using System.Collections.Generic;

public class Solution {
// Base case
if (words == null || words.Length == 0) {
return new List();
}

// Sort the array by length so that we can early terminate
// when we encounter a word that is too short to be a concatenated word
Array.Sort(words, (a, b) => a.Length - b.Length);

// Use a set to keep track of all the valid words
// This allows us to check if a word is valid in constant time
var set = new HashSet(words);

// Use a list to keep track of all the concatenated words
var result = new List();

// Iterate through all the words
for (int i = 0; i < words.Length; i++) {
// If the current word has already been processed, we can skip it
if (i > 0 && words[i] == words[i - 1]) {
continue;
}

// If the current word is too short to be a concatenated word, we can early terminate
if (isConcatenatedWord(words[i], set, 0)) {
}
}

return result;
}

// Helper function to check if a word is a concatenated word
private bool isConcatenatedWord(string word, HashSet set, int start) {
// Base case
if (start == word.Length) {
return false;
}

// Iterate through all possible prefixes of the current word
for (int end = start + 1; end <= word.Length; end++) {
// If the current prefix is a word, we recurse on the remaining suffix
if (set.Contains(word.Substring(start, end - start))) {
// If the remaining suffix is also a concatenated word, then the current word is a concatenated word
if (end == word.Length || isConcatenatedWord(word, set, end)) {
return true;
}
}
}

// If we've checked all possible prefixes and haven't found a concatenated word,
// then the current word is not a concatenated word
return false;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]