用Python查找和分组anagram

Question

input: ['abc', 'cab', 'cafe', 'face', 'goo']
output: [['abc', 'cab'], ['cafe', 'face'], ['goo']]

问题很简单：它按anagrams分组。顺序无关紧要。

当然，我可以用C++来做这（这是我的母语）。但是，我想这可以通过Python在一行中完成。编辑：如果不可能的话，可以写两三行。我是Python新手。

为了检查两个字符串是否是anagram，我使用了sorting。

>>> input = ['abc', 'cab', 'cafe', 'face', 'goo']
>>> input2 = [''.join(sorted(x)) for x in input]
>>> input2
['abc', 'abc', 'acef', 'acef', 'goo']

我认为结合map左右是可行的。但是，我需要使用dict作为哈希表。我还不知道这一行是否可行。任何提示都会被告知！

Answer 1

可读的单行解决方案：

output = [list(group) for key,group in groupby(sorted(words,key=sorted),sorted)]

例如：

>>> words = ['abc', 'cab', 'cafe', 'goo', 'face']
>>> from itertools import groupby
>>> [list(group) for key,group in groupby(sorted(words,key=sorted),sorted)]
[['abc', 'cab'], ['cafe', 'face'], ['goo']]

这里的关键是使用^{} from the ^{} module将列表中的项组合在一起。

我们提供给groupby的列表必须进行高级排序，以便我们通过sorted(words,key=sorted)。这里的诀窍是sorted可以接受一个键函数，并根据该函数的输出进行排序，因此我们再次将sorted作为键函数传递，这将使用字符串的字母按顺序对单词进行排序。不需要定义自己的函数或创建lambda。

groupby接受一个键函数，它用来告诉是否应该将项组合在一起，然后我们可以再次将内置的sorted函数传递给它。

最后要注意的是输出是一对键和组对象，所以我们只需要取grouper对象并使用list函数将它们转换成一个列表。

（顺便说一下，我不会像调用隐藏变量input那样调用它，尽管它可能不是您应该使用的变量。）

Answer 2

无法阅读的单行解决方案：

>>> import itertools
>>> input = ['abc', 'face', 'goo', 'cab', 'cafe']
>>> [list(group) for key,group in itertools.groupby(sorted(input, key=sorted), sorted)]
[['abc', 'cab'], ['cafe', 'face'], ['goo']]

（好吧，如果算上导入的话，实际上是2行……

Answer 3

不是一句话而是一个解决方案。。。

d = {}
for item in input:
  s = "".join(sorted(item))
  if not d.has_key(s):
    d[s] = []
  d[s].append(item)
input2 = d.values()