连接词

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)

解法