Concatenated Words - Leetcode Solution

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[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:

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^2*m) 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[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.

1