查找给定的最长单词

查找给定的最长单词

没有Java代码。您可以自己解决。

假设我们需要做很多次，这就是我要做的：

• 我将从为字典中的每个单词（由26位组成）创建“签名”开始，其中如果单词包含一个（或多个）字母实例，则设置bit [letter]。这些签名可以编码为Java

  int

  。

• 然后创建一个映射，将签名映射到具有该签名的单词列表。

要使用预先计算的地图进行搜索：

• 为要为其查找单词的字母集创建签名。

• 然后遍历映射的键，查找其中的键

  (key & (~signature) == 0)

  。这样就为您提供了一个“可能”的简短列表，其中不包含不在所需字母集中的任何字母。

• 遍历简短列表以查找每个所需字母的 正确编号 的单词，记录最长的匹配记录。

---

笔记：

1. 虽然主要搜索大致

   O(N)

   取决于字典中的单词数，但该测试非常便宜。

2. 这种方法的优点是需要相对较小的内存中数据结构（很可能具有良好的局部性）。这可能有助于更快的搜索。

---

这是加快上述

O(N)

搜索步骤的一种方法。

从上面的签名图开始，为 确实
包含特定成对字母的所有单词创建（预计算）派生图；即，一个用于包含AB的单词，一个AC，BC，…和YZ。然后，如果您要查找包含（例如）P和Q的单词，则只需扫描PQ导数图即可。这将减少

O(N)

了大约一步

26^2

......在更多内存的额外地图的成本。

可以扩展到3个或更多字母，但是缺点是内存使用量激增。

另一个潜在的调整是（以某种方式）使初始字母对的选择偏向于不经常出现的字母/对。但这增加了前期开销，该开销可能大于通过搜索较短列表而获得的（平均）节省。