3

给定一个由字符 AZ 组成的最长 25 个字符的输入字符串，在输入字符串的所有可能字谜的字母排序列表中输出其索引。输入字符串不区分大小写。输入字符可以重复。该应用程序必须在 500 毫秒内完成并且占用少于 1GB 的内存。

乍一看，如果没有任意精度的数学库，这似乎是不可能的。最坏情况输入是 25 个唯一字符，结果为 25！可能的字谜。25！比 2^64 大几个数量级。因为索引和字符串之间的关系不是直接的，必须计算出来，所以没有办法简单地将字符串转换为数字。

这来自我前几天收到的一个面试挑战。我无法为他们想出一个解决方案，他们坚持认为确实有一个很好的解决方案......

4

1 回答 1

8

给定一个单词的字母频率，很容易计算单词的字谜数。它是字符总数的阶乘除以频率的阶乘，这些数字也称为多项式系数。

使用这个事实，您可以通过按字母顺序计算前缀的字谜数来获得任何字谜的索引。例如，以密西西比州为例：字母频率为 I: 4, M: 1, P: 2, S: 4，总共 11!/(4!1!2!4!) = 34650 个字谜。

  • 以 I 开头的字谜的数量是 10!/(3!1!2!4!) = 12600
  • 以 MII 开头的字谜的数量是 8!/(2!0!2!4!) = 420
  • 以 MIP 开头的字谜的数量是 8!/(3!0!1!4!) = 280
  • 以 MISI 开头的字谜的数量是 7!/(2!0!2!3!) = 210
  • 以 MISP 开头的字谜的数量是 7!/(3!0!1!3!) = 140
  • 以 MISSII 开头的字谜的数量是 5!/(1!0!2!2!) = 30
  • 以 MISSIP 开头的字谜的数量是 5!/(2!0!1!2!) = 30
  • 等等...

把这些数字加起来，你就得到了索引。但是，是的，您可能需要一些任意精度的数字库，因为正如您所说，在最坏的情况下有 25 个！字谜和索引可能超出 64 位整数的范围。

不过，这感觉不是很优雅，如果有更好的解决方案，我很想听听。

于 2013-09-05T21:20:19.033 回答