🐾 词链接龙记

（Rabbit‑Cat Informatics Academy · 加菲老师特训）

故事背景

又是一节欢乐的单词课！加菲老师拿出一摞纸条，上面写满了小写英文字母组成的单词。“小兔、小猫，今天的任务是词链接龙！”

“规则很简单，”加菲老师眯起眼睛解释，“如果在单词 A 的任意位置插入恰好一个字母且不打乱其它字母顺序，就能得到单词 B，那么我们说 A 是 B 的前身。 例如：abc ➜ abac 是前身关系，但 cba ➜ bcad 不是，因为顺序被破坏了。” 小兔举起爪爪：“我们要把纸条排成尽可能长的链，对吧？” “没错！你俩快用程序帮我算出能得到的最长词链长度。” 于是，本题诞生……

---

题目描述

给定一个单词数组 $words$，其中每个单词仅包含小写英文字母。 若存在单词 $word_A,,word_B$ 使得通过在 $word_A$ 任意位置插入 恰好一个 字母（不改变其他字符的相对顺序）即可变为 $word_B$，则称 $word_A$ 为 $word_B$ 的 前身。

把若干单词排成序列 $\[word\_1,word\_2,\dots ,word\_k]\$（\$k\ge1\$），使得$word_i \text{ 是 } word_{i+1} \text{ 的前身}\quad(1\le i<k).$ 这样的序列称为词链。单个单词本身视作长度 $1$ 的词链。

请你从给定列表中选取单词，构造一条最长词链并输出其长度。

---

输入格式

n
word_1 word_2 … word_n

• $n$ — 单词数量。
• 接下来一行给出 $n$ 个由小写英文字母组成的单词，空格分隔。

输出格式

ans

• ans — 通过最优构造得到的最长词链长度。

---

样例

6
a b ba bca bda bdca

4

样例解释 1

可行链之一：a → ba → bda → bdca，长度 $4$。

---

5
xbc pcxbcf xb cxbc pcxbc

5

样例解释 2

可行链：xb → xbc → cxbc → pcxbc → pcxbcf，长度 $5$。

---

数据范围

参数	取值范围
$1 \le n \le 1000$
$1 \le	word_i	\le 16$
$word_i$ 仅含 a–z

---

✨ 标准解题思路

1. 按长度递增排序所有单词。

2. 哈希表 dp[word] 记录以该单词为结尾的最长链长度。

3. 对每个单词 w，枚举删去任一字符得到的前驱 pre：

   • 若 pre 在哈希表中出现，则 dp[w] = max(dp[w], dp[pre]+1)；
   • 否则 dp[w] 至少为 1。

4. 答案是所有 dp 中的最大值。

复杂度：

• 枚举删除字符 $\le16$ 次，故总时间 $O(\sum |word_i|) \le 16000$。
• 空间 $O(n)$。