Description
Given an array of strings words, return all concatenated words in the array. A concatenated word is formed by concatenating at least two shorter words from the array.
Examples
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]["catsdogcats","dogcatsdog","ratcatdogcat"]Three words can be formed by concatenating shorter words: 'catsdogcats' = 'cats' + 'dog' + 'cats' (or 'cat' + 's' but 's' isn't in the list, so we use 'cats'+'dog'+'cats'). 'dogcatsdog' = 'dog' + 'cats' + 'dog' (or 'dog'+'cat'+'s'+'dog' but we need valid words). 'ratcatdogcat' = 'rat' + 'cat' + 'dog' + 'cat'. Note that 'hippopotamuses' cannot be formed from any combination of the other words.
words = ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa"]["aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa"]Every word except 'a' is a concatenated word: 'aa' = 'a'+'a', 'aaa' = 'a'+'a'+'a' or 'a'+'aa', 'aaaa' = 'aa'+'aa' or 'a'+'aaa', and so on. The base word 'a' cannot be formed from other words since it's the shortest. This tests the algorithm's ability to handle multiple valid decompositions.
words = ["tech","lead","tripadvisor","techno","lead","tech","ninja","techninja"]["techninja"]Only "techninja" is a concatenated word, formed by combining "tech" + "ninja". Note that "techno" cannot be formed from the available words since "no" is not in the array, and duplicate words like "lead" and "tech" don't affect the result.
Constraints
- •
1 ≤ words.length ≤ 10⁴ - •
1 ≤ words[i].length ≤ 30