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.