Given a list of words, return all words that can be formed by concatenating at least two shorter words from the same list. Pattern focus: Trie DFS Search. DFS with memoization lets you test whether a word can be composed from previously inserted dictionary pieces.
words = array of lowercase words
all concatenated words in lexicographic order
Example 1:
Input:
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output:
[catsdogcats,dogcatsdog,ratcatdogcat]
Explanation:
Each returned word can be built from at least two smaller dictionary words.
Example 2:
Input:
words = ["cat","dog"]
Output:
[]
Explanation:
No word can be formed by combining two or more shorter words.
Example 3:
Input:
words = ["a","aa","aaa","aaaa","aaaaa"]
Output:
[aa,aaa,aaaa,aaaaa]
Explanation:
Every word longer than one character can be decomposed into smaller dictionary pieces.