<p>除非我误解了这个问题,否则简单地通过对单词的字符进行排序来对单词进行分组应该是一个有效的解决方案,正如您已经意识到的那样。诀窍是避免将每个单词与其他所有单词进行比较。以字符排序的字符串为关键字的dict可以快速找到每个单词的正确组;查找/插入将是O(logn)。你知道吗</p>
<pre><code>#!/usr/bin/env python3
#coding=utf8
from sys import stdin
groups = {}
for line in stdin:
w = line.strip()
g = ''.join(sorted(w))
if g not in groups:
groups[g] = []
groups[g].append(w)
for g, words in groups.items():
if len(words) > 1:
print('%2d %-20s' % (len(words), g), ' '.join(words))
</code></pre>
<p>在我的words文件(99171个单词)上测试,似乎效果不错:</p>
<pre><code>anagram$ wc /usr/share/dict/words
99171 99171 938848 /usr/share/dict/words
anagram$ time ./anagram.py < /usr/share/dict/words | tail
2 eeeprsw sweeper weepers
2 brsu burs rubs
2 aeegnrv avenger engrave
2 ddenoru redound rounded
3 aesy ayes easy yeas
2 gimnpu impugn umping
2 deeiinsst densities destinies
2 abinost bastion obtains
2 degilr girdle glider
2 orsttu trouts tutors
real 0m0.366s
user 0m0.357s
sys 0m0.012s
</code></pre>