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.
