finding the longest word made by concatenating other words from a list

Problem

Given a list of words, find the longest word that can be made by concatenating other words from the list.
Example input:
words = ["cat", "cats", "dog", "dogs", "pig", "pigs"]
Example output:
"catsdogspigs"

Solution

This solution is in Python. Our A.I. can create solutions in multiple languages.

kayakane

# Solution:
# The optimal solution is to sort the list of words by length, and then iterate through the list, checking if the word can be made by concatenating other words from the list.
# This solution is optimal because it only requires one pass through the list of words, and the sorting is done in O(n log n) time.

def longest_word(words):
    words.sort(key=len, reverse=True)
    for word in words:
        if can_make_word(word, words):
            return word
    return None

def can_make_word(word, words):
    if len(word) == 0:
        return True
    for i in range(1, len(word) + 1):
        if word[:i] in words and can_make_word(word[i:], words):
            return True
    return False

words = ["cat", "cats", "dog", "dogs", "pig", "pigs"]
print(longest_word(words))