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
Input:
words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]Output:
["catsdogcats","dogcatsdog","ratcatdogcat"]Explanation:
Catsdogcats=cats+dog+cats, dogcatsdog=dog+cats+dog, ratcatdogcat=rat+cat+dog+cat. Each uses 2+ words from array.
Input:
words = ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa"]Output:
["aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa"]Explanation:
Aa=a+a, aaa=a+aa, etc. Every word except 'a' can be formed from smaller words. 'a' is the base.
Input:
words = ["tech","lead","tripadvisor","techno","lead","tech","ninja","techninja"]Output:
["techninja"]Explanation:
Techninja=tech+ninja. 'techno' fails (no 'no' in array). 'tripadvisor' also not composable.
Constraints
- •
1 ≤ words.length ≤ 10⁴ - •
1 ≤ words[i].length ≤ 30