#!/usr/bin/env python3

# Find the longest word that is made of other words in a list.

def canSplit(word, words, isFirst, missed):
    if not isFirst and word in words:
        return True
    for i in range(len(word)):
        left, right = word[:i], word[i:]
        if (left in words and right not in missed
                and canSplit(right, words, False, missed)):
            return True
    missed.add(word)
    return False


def longestComb(words):
    words.sort(key=len, reverse=True)
    # Since sorted by len, first canSplit() == True
    # is the longest word that can be split.
    for word in words:
        if canSplit(word, set(words), True, set()):
            return word


def run():
    words = ['cat', 'banana', 'dogwalkercat', 'somethinglong12',
            'walker', 'dog', 'walk', 'nana', 'walkdog']
    print(longestComb(words))


if __name__ == '__main__':
    run();