P2817. 单词接龙

解题思路

题意理解

首先必须避免一个题目理解上的误区。 假设已知当前的已经接龙好的字符串为 ans，其最后一个字符为 ans[-1]。 那么下一个接龙的单词，是首字母为 ans[-1] 的长度尽可能大、字典序尽可能小的那个单词。

换句话说，对于已经接龙好的字符串为 ans，其下一个接龙的单词是唯一确定的。

此处可能存在另一种理解，就是接龙过程中选择单词的策略是不确定的，目的是使得最终接龙完毕的字符串最长。如果是这种理解，则示例二的答案会是 dwordddda，需要使用动态规划来完成，难度陡升。

同一首字母的单词列表排序

由于每一次接龙之后，下一个接龙的单词的首字母就是当前字符串的最后一个字母 ans[-1]。 假设以字母 ans[-1] 为开头的单词已经储存为一个列表 lst。 我们需要找到 lst 中，长度尽可能大、字典序尽可能小的那个单词。 可以使用 lambda 匿名函数对 lst 进行排序，lst 末尾的元素就是要延长的单词。

上述排序写法可能不容易理解，举个例子就好理解了。 对于以 "a" 为开头的若干单词 lst = ["a", "ab", "ac", "abd", "abc"]，我们期望其获得如下排序：

lst.sort(key = lambda x: (-len(x), x)) 的含义是，先按照长度从大到小排序，长度相等的时候再按照字典序从小到大排序。这样排序后，具有最高优先级的单词就排在 lst 的开头了。 为了使得具有最高优先级的单词排在 lst 的末尾，方便使用 pop() 操作取出，我们在排序的过程中再设置参数 reverse = True，即 lst.sort(key = lambda x: (-len(x), x), reverse = True)，这样就能达到排序要求。

以首字母分类单词构建哈希表

很显然，所有具有同一个首字母的单词都可以分为同一组，放在同一个列表中进行排序。 所以我们可以构建哈希表 dic，key 为首字母 first_ch，value 为以字母 first_ch 为首字母开头的若干单词构成的列表。对应的代码如下：

除此之外，dic 中的每一个列表都要再按照前一小点中的排序方案进行排序，即：

譬如对于示例二，构建出来的 dic 如下：

单词接龙模拟过程

在上述预处理过程完成之后，剩下就是按照题意进行单词接龙的模拟过程了。

显然这里的循环过程不应该使用 for 循环（因为不知道接龙次数），应该使用 while 循环。 当前字符串 ans 的最后一个字母 ans[-1] 是下一个单词的首字母，因此我们 while 持续进行的条件是，首字母 ans[-1] 在 dic 中还能找到对应的单词，即 len(dic[ans[-1]]) > 0。

在循环中，由于前面预处理已经将每一个单词列表都按照要求排序完毕，我们需要弹出列表 dic[ans[-1]] 中的最后一个单词，作为接下来延长的单词 following_word = dic[ans[-1]].pop()。

对 ans 进行延长就是直接 ans += following_word。

故代码为：

复杂度分析 设单词个数为 n，最长单词长度为 m，所有单词的总字符数为 L（L <= n*m）。

• 读入并按首字母分组进哈希表：每个单词 O(1) 次追加，连读入字符一起算是 O(L)。
• 预排序：对每个首字母的列表按（长度降序、字典序升序）排序，排序比较的键含字符串本身，单次比较最坏 O(m)；所有组的规模加起来是 n，故这一步总计 O(n * m * log n)，是整个算法的瓶颈。
• 接龙模拟：while 循环每轮从对应列表 pop() 弹出一个单词，每个单词至多被弹出一次，循环至多执行 n 轮，拼接的总字符量不超过 L。

总时间复杂度 O(n * m * log n)，空间复杂度 O(L)，即哈希表里存放全部单词的开销。得益于"先把每组排好序、接龙时只从末尾弹出"的设计，模拟阶段本身是线性的。