从字典中获取字谜列表

Question

基本上,字谜像string.Eg的置换stack,sackt,stakc所有都是字谜stack(上面的字认为是没有意义的).无论如何你可以理解我的意思.

现在,我想要一个anagrams给定百万字的列表或者只是从字典中说出来.

我的基本问题是 Find total number of unique anagrams in a dictionary?

排序和比较不起作用,因为它的时间复杂性非常糟糕.

我想过使用哈希表,字符串作为键.

但问题是哈希函数应该是什么？如果提供一些伪代码将会有所帮助.比提到的方法更好的一些其他方法也会有所帮助.

谢谢.

Answer 1

显而易见的解决方案是将每个字符映射到素数并乘以素数.所以,如果'a'' - > 2和'b' - > 3,那么

• 'ab' - > 6
• 'ba' - > 6
• 'bab' - > 18
• 'abba' - > 36
• 'baba' - > 36

为了最小化溢出的可能性,可以将最小的素数分配给更频繁的字母(e,t,i,a,n).注意:第26个素数是101.

更新: 可以在此处找到实现