P2704. 寻找密码

解题思路

最朴素的解法是将所有字符串存在一个哈希表 password_set 中，然后遍历字符串数组中的每一个密码 password，对每一个 password 都去判断其所有的前缀是否也位于 password_set 中。如果满足，则把 password 和 ans 比较并且更新 ans。

这种做法虽然思路直接简单，但略显笨重，会出现很多重复计算。

以示例一为例子：

• 对于单词 hell，需要分别考虑前缀 h、he、hel
• 对于单词 hello，需要分别考虑前缀 h、he、hel、hell

前缀 h、he、hel 对于单词 hello 而言，显然是重复计算了。

假设我们已经知道单词 hell 是一个有效的密码，那么对于单词 hello，我们就只需要去考虑 hell 这个前缀，而不需要再去考虑 h、he、hel 这三个前缀了。

换句话说，单词 hello 是否是一个有效的密码，可以由其去掉末尾的前缀 hell 是否是一个有效的密码来决定。这本质上是一种动态规划的思想。（动态规划更详细的内容在后面会讲到）

如果用动态规划的语言来描述，即：password 是一个有效密码，当且仅当 password[:-1] 是一个有效密码。

那么现在问题就变成了：如何能够在判断 password 是一个有效密码之前，就先判断得到 password[:-1] 是否有效？这个问题就很简单了。我们只需要对原来的字符串数组 password_lst 按照字典序进行排序，就可以保证在 password 进行判断时，password[:-1] 已经被判断过了。

我们可以构建一个用于储存所有有效密码的哈希集合 valid_set。然后遍历排序过的字符串数组 password_lst 中的每一个密码 password，如果其去掉末尾的前缀 password[:-1] 位于 valid_set 中，说明 password 也是一个有效密码，需要将其加入 valid_set 中，同时更新 ans。

注意 valid_set 初始化时要包含一个空串 ""，因为只有一个字符的密码比如 "h"，去掉最末尾的字符之后是一个空串 ""，"h" 理应是一个有效的密码，故 "" 应该存在于 valid_set 中。即：

代码

解法一：哈希集合暴力解

（哈希集合暴力解法，只能通过部分用例）

复杂度分析

设密钥库中有 n 个密钥，最长密钥长度为 L。

以参考代码（解法一，哈希集合暴力解）为准：

• 建哈希集合：把 n 个密钥逐个放入 HashSet，每个字符串求哈希要扫一遍字符，这一步是 O(n*L)。
• 逐个校验：对每个密钥要枚举它的所有真前缀（最多 L-1 个），substring 取前缀本身是 O(L)，在 HashSet 中查找又要对前缀求哈希 O(L)，所以单个密钥的校验最坏是 O(L^2)，n 个密钥合计 O(n*L^2)。这就是整个算法的瓶颈，密钥较长时会超时，正文所说“只能通过部分用例”的原因正在于此。
• 空间：HashSet 存放全部密钥，O(n*L)。

正文中的改进思路（先按字典序排序，再用 valid_set 只检查“去掉末尾一位”的前缀）把每个密钥的校验从最多 L-1 次前缀查找降为 1 次：排序是 O(n log n * L)（字符串比较最坏 O(L)），随后一趟遍历中每个密钥只做一次 O(L) 的切片与哈希查找，共 O(n*L)。总时间 O(n log n * L)，空间同样是 O(n*L)，明显优于暴力解。