连接词

472. 连接词 (Hard)

给定一个 不含重复 单词的字符串数组 words ，编写一个程序，返回 words 中的所有 连接词 。

连接词 的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。

 

示例 1：

输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出：["catsdogcats","dogcatsdog","ratcatdogcat"]
解释："catsdogcats"由"cats", "dog" 和 "cats"组成; 
     "dogcatsdog"由"dog", "cats"和"dog"组成; 
     "ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。

示例 2：

输入：words = ["cat","dog","catdog"]
输出：["catdog"]

 

提示：

• 1 <= words.length <= 104
• 0 <= words[i].length <= 1000
• words[i] 仅由小写字母组成
• 0 <= sum(words[i].length) <= 6 * 105

相关话题

[深度优先搜索] [字典树] [字符串] [动态规划]

相似题目

1. 单词拆分 II (Hard)

---

解法