Find all concatenated words in a given list of words

This is a Leetcode problem –

Given a list of words (without duplicates), 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.

Note –

• The number of elements of the given array will not exceed `10,000`.
• The length sum of elements in the given array will not exceed `600,000`.
• All the input string will only include lower case letters.
• The returned order of elements does not matter.

Here is my solution to this challenge (in Python) –

``def find_all_concatenated_words_in_a_dict(words):     """     :type words: List[str]     :rtype: List[str]     """     words = set(words)     output = []      def check(word):         for i in range(len(word) - 1):             if word[i+1:] in words:                 return True             elif check(word[i+1:]):                 return True         return False      for word in words:         if check(word):             output.append(word)     return output ``

Here is an example output –

``#print(find_all_concatenated_words_in_a_dict(["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]))  >>> ['catsdogcats', 'ratcatdogcat', 'dogcatsdog'] ``

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"`.

Here is the time taken for this output –

``%timeit find_all_concatenated_words_in_a_dict(["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"]) 7.84 ms ± 143 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) ``

So, I would like to know whether I could make this program shorter and more efficient.