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

Step by Step Implementation For Concatenated Words

import java.util.*;

public class Solution {
    public List findAllConcatenatedWordsInADict(String[] words) {
        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)) {
                result.add(words[i]);
            }
            preWords.add(words[i]);
        }

        return result;
    }

    private boolean canForm(String word, Set dict) {
        if (dict.isEmpty()) return false;
        boolean[] dp = new boolean[word.length() + 1];
        dp[0] = 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[0] = 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:
    vector findAllConcatenatedWordsInADict(vector& words) {
        unordered_set s(words.begin(), words.end());
        vector res;
        for (string& word : words) {
            int n = word.size();
            vector dp(n + 1);
            dp[0] = 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 {
    public IList FindAllConcatenatedWordsInADict(string[] words) {
        // 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)) {
                result.Add(words[i]);
            }
        }
        
        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;
    }
}