【综合笔试题】难度 3.5/5，常见序列 DP 题目及其优化思路

题目描述

这是 LeetCode 上的「472. 连接词」，难度为「困难」。

Tag : 「字符串哈希」、「序列 DP」

给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。

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

示例 1：

代码语言：javascript复制

输入：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：

代码语言：javascript复制

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

输出：["catdog"]

提示：

1 <= words.length <= 10^4

0 <= words[i].length <= 1000

• words[i] 仅由小写字母组成

0 <= sum(words[i].length) <= 10^5

序列 DP 字符串哈希

给定数组 words，先考虑如何判断某个 s = words[i] 是否为「连接词」。

为了方便，我们称组成 s 的每个连接部分为 item。

举个