1

我有一些字母和频率计数。我有一个很长的单词列表（1M 说）。

假设我有A-1, B-1, D-1（“最多一个A，最多一个B，最多一个D”），那么我可以制作"BAD"，但不能"RAD"

我可以知道哪些单词可以由这些字母组成，在对数时间内，或者类似的时间，而不是遍历所有单词并查看单词中每个字母的计数？

这些词可以使用什么数据结构？试试吧？我不知道他们。如果我可以用它存储每个单词所需的字母，那也很棒。请帮忙！

4

3 回答 3

3

这是数据结构的（字面）草图。

             [root]
         ----- | -----
       A1      A2     B1 ...
  ----/-    ---|---    -\----
 B1 C1 [a]  B1 B2 C1  C1 C2 D2 ...

它是一棵树，其中叶节点是单词列表中的单词。叶节点上的单词完全由字母袋组成，字母袋包含从根到该节点的路径。非叶节点用字母和计数标记。一个节点的子节点必须要么是叶子（一个词），要么在字母表中严格地有一个字母。所以，要找到“猫”，你要走这条路A1,C1,T1，并且cat（和act）将成为 T1 的孩子。在每个节点，您遍历 count ≤ 您的输入计数的子节点（因此对于 bag A3, C1, T2，您将遍历标记为 A1、A2、A3、C1、T1 或 T2 的任何节点）。

在最坏的情况下（每个单词都匹配），遍历需要 O(n) 时间，但平均而言需要更少的时间。对于一个小的输入包，它只会遍历几个节点。对于一个大的输入包，它会遍历很多节点，但也会找到很多单词。

树在词表中每个字母最多包含一个节点，因此它的大小最多与词表的长度成正比。

这是一种节省时间和空间的结构，可以相对容易地计算和存储——它不会比你的单词表占用更多的空间，而且查询速度非常快。

于 2013-02-10T03:47:20.190 回答
1

如果您需要包含所有字母的单词，我以前做过类似的事情（我的填字游戏作弊程序，我很惭愧地说）。

我拿了一个字典文件并对其进行了预处理，因此每一行都对字母进行了排序，然后是单词本身，例如：

aaadkrrv:aardvark

然后，如果您有字母ardvkraa，请对其进行排序，然后在冒号之前查找包含该字符串的行。我使用grepO(n) 已经足够好，但是您可以轻松地将所有行放入平衡的二叉树中，从而为您提供 O(log n) 复杂度。

如果您要查找仅使用某些字母的单词，那将无济于事，但尚不清楚这是否是您想要的。

于 2013-02-10T03:23:27.280 回答
0

我不能说我可以从您的描述中 100% 掌握您提出的问题，但据我所知，您可以执行以下操作：

你索引你的单词列表。例如，“B1”是一个索引，它将包含一个条目列表，其中包含不超过一个字母 B，或者满足您正在解决的问题的要求。您还可以使用“复合”索引，例如“A1B1”。鉴于您可以负担索引的时间预算，您可以创建非常深的哈希值。如果您使用 26 个字母的字母表并想要对 4 个字母组合进行散列，则只有 14,950 个索引，如果是 3 个字母，则只有 2,600 个。可以在列表的一次迭代中构建索引，因此它们的创建是线性的。一旦你过了这个阶段，你的大部分查找将是对数的。在我的示例中，您的 4 个字母单词查找将是一次提取。当然，

于 2013-02-10T04:01:15.707 回答