We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Concatenated Words

Number: 472

Difficulty: Hard

Paid? No

Companies: Amazon, Salesforce, eBay, TikTok, Microsoft

Problem Description

Given an array of unique strings, return all the concatenated words in the list. A concatenated word is defined as a string that is comprised entirely of at least two shorter words from the given array.

Key Insights

  • Sort the words by length so that smaller words, which can be used to build larger ones, are processed first.
  • Use dynamic programming to determine if a given word can be segmented into two or more words from a pre-built dictionary (set).
  • Ensure that when checking a word, you do not consider the word itself; only use previously seen (shorter) words.
  • Optimize by limiting the inner loop based on the maximum possible word length (given constraint is 30).

Space and Time Complexity

Time Complexity: O(n * l^2) where n is the number of words and l is the average length of the words. Space Complexity: O(n * l) for storing words and the DP array for each word.

Solution

The solution involves first sorting the list of words by their length. For each word, use a DP array where dp[i] indicates whether the substring word[0:i] can be constructed from words in a set of previously seen words. If a word can be segmented into at least two parts based on the dictionary, it qualifies as a concatenated word. After processing each word, add it to the set so that it can be used to form longer words. This approach effectively builds up from the smallest words to the largest.

Code Solutions

def findAllConcatenatedWordsInADict(words):
    # Sort the words by length to ensure that smaller words are processed first.
    words.sort(key=len)
    concatenated = []
    word_set = set()

    # Function to check if the word can be formed by words in the set.
    def can_form(word):
        if not word:
            return False
        dp = [False] * (len(word) + 1)
        dp[0] = True
        # Try all possible splits.
        for i in range(1, len(word) + 1):
            # Limit inner loop based on maximum word length of 30.
            for j in range(max(0, i - 30), i):
                if dp[j] and word[j:i] in word_set:
                    dp[i] = True
                    break
        return dp[len(word)]
    
    # Process each word.
    for word in words:
        if not word:
            continue
        if can_form(word):
            concatenated.append(word)
        word_set.add(word)
    
    return concatenated

# Example usage:
words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]
print(findAllConcatenatedWordsInADict(words))
← Back to All Questions