从字典中获取卦词列表 [英] get list of anagrams from a dictionary

问题描述

基本上，Anagrams就像string.Eg stack ， sackt ， stakc的排列都是 stack （以上单词无意义）的卦。无论如何，你可以理解我的基本意图。

现在，我想要一个 anagrams

我的基本问题是在字典中查找唯一的卦词总数

排序和比较
将无法正常工作，因为它的时间复杂度很差。

我想到使用哈希表，字符串作为键。

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

谢谢。

解决方案>

明显的解决方案是将每个字符映射到素数，并乘以素数。那么如果'a'' - > 2和'b' - > 3，那么

• 'ab' - > 6


• 'ba' - > 6


• 'bab' - > 18


• 'abba' - > 36


• 'baba' - > 36

为了最小化溢出的机会，可以分配最小的素数更频繁的字母（e，t，i，a，n）。注意：第26个素数是101。

更新：
实施可以在这里找到

Basically, Anagrams are like permutation of string.E.g stack ,sackt ,stakc all are anagrams of stack (thought above words aren't meaningful). Anyways you could have understood what I basically meant.

Now, I want a list of anagrams given million words or simply say from a dictionary.

My basic question is Find total number of unique anagrams in a dictionary?

Sorting and comparing won't work as it's time complexity is pretty bad.

I thought of using hash table, string as key.

But the problem is what should be the hash function ? It would be helpful if some pseudocode provided. Some other approaches better than mentioned approaches would also be helpful.

Thanks.

解决方案

The obvious solution is to map each character to a prime number and multiply the prime numbers. So if 'a'' -> 2 and 'b' -> 3, then

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

To minimise the chance of overflow, the smallest primes could be assigned to the more frequent letters (e,t,i,a,n). Note: The 26th prime is 101.

UPDATE: an implementation can be found here

这篇关于从字典中获取卦词列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！