## Similar Problems

Similar Problems not available

# Concatenated Words - Leetcode Solution

LeetCode: Concatenated Words Leetcode Solution

Difficulty: Hard

Topics: string dynamic-programming depth-first-search array

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:

- Sort the input list of words by their length.
- For each word in the list, check if it can be formed by concatenating one or more shorter words.
- 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[0] 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:

- Sorting the input list of words takes O(n log n) time.
- Checking if a word can be formed by concatenating shorter words takes O(n^2*m) time, where n is the length of the word and m is the average length of words in the input list.
- 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[0] = 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.

## Concatenated Words Solution Code

`1`