给定一个由字符 A-Z 组成的最长 25 个字符的输入字符串，输出其在输入字符串所有可能的字谜词按字母顺序排序的列表中的索引。输入字符串不区分大小写。输入的字符可以重复。该应用程序必须在 500 毫秒内完成，并且占用的内存少于 1GB。
乍一看，如果没有任意精度的数学库，这似乎是不可能完成的。最坏的情况输入是 25 个唯一字符，结果是 25！可能的字谜。 25！比 2^64 大几个数量级。因为索引和字符串之间的关系不是直接的，必须计算，所以没有办法简单地将字符串转换为数字。
这来自我前几天收到的面试挑战。我无法为他们想出解决方案，但他们坚持认为确实有一个好的解决方案......
给定单词的字母频率，很容易计算出该单词的字谜词数。它是字符总数的阶乘除以频率的阶乘，这些数字也称为多项式系数 http://en.wikipedia.org/wiki/Multinomial_theorem#Number_of_unique_permutations_of_words.
利用这一事实，您可以通过计算按字母顺序排列在其前面的前缀的 anagram 数量来获取任何 anagram 的索引。以 MISSISSIPPI 为例：字母出现频率为 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 位整数的范围。
但这感觉不太优雅，如果有更好的解决方案，我很乐意听到。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
