查找数量的字典

Question

以下是在一次采访中向我询问的问题。 我们知道食物的一种是：茶和吃 现在的问题是： 我们有一个程序。我们向该计划提供一万个字母的列表。 我们运行该程序。 现在在运行时，我们为这个程序提供一个词，例如。 “eat” 现在程序应该返回一万个字母列表中存在的anagrams的数量。因此，对于“吃”的输入，它应该返回2.

什么将是存储那些10000个字母，以便找到字谜的数量变得容易策略。

Answer 1

令每个单词的字母，以减少它的排序规则，即tea变得aet。

然后，只需把这些单词中的一个（哈希）地图计数（包括tea和ate映射到aet，所以我们会在地图上有(aet, 2)）

然后，当你得到一个字，重新排序如上所述的字母，并对count进行查找。

运行时间：

假设n词语的列表，以及m的平均字长...

预计O(nm log m)预处理，预计O(m log m)每次查询。

这是m log m上，我们只是做一个简单的排序一个单词的字母的假设。

每个查询所花费的时间预计将在列表中的字的数量的影响（即，哈希映射就给预期O(1)查找时间）。