algorithm - 查找字谜的数量

Question

以下是我在一次采访中被问到的一个问题。我们知道吃的字谜是：茶和吃 问题是：我们有一个程序。我们向这个程序提供了一个包含 10,000 个字母的列表。我们运行程序。现在在运行时，我们为这个程序提供一个词，例如。“吃” 现在程序应该返回 10,000 个字母列表中存在的字谜的数量。因此，对于“吃”的输入，它应该返回 2。

存储这 10,000 个字母的策略是什么，以便查找字谜的数量变得容易。

Answer 1

对每个单词的字母进行排序以使其排序最小化，即tea变为aet。

然后简单地将它们放在单词的（散列）映射中以计数（两者都tea映射ate到aet，所以我们将(aet, 2)在映射中）

然后，当你得到一个单词时，像上面那样重新排列字母并查找计数。

运行时间：

假设n列表中的单词，平均单词长度为m...

预期O(nm log m)的预处理，预期O(m log m)的每个查询。

这是m log m假设我们只是对单词的字母进行简单排序。

每个查询花费的时间预计不受列表中单词数量的影响（即散列图给出预期的O(1)查找时间）。