# Source code for tryalgo.anagrams

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Anagrams
christoph dürr - jill-jênn vie - 2013-2019
"""
# snip{
# pylint: disable=anomalous-backslash-in-string
[docs]
def anagrams(S): # S is a set of strings
"""group a set of words into anagrams
:param S: set of strings
:returns: list of lists of strings
:complexity:
:math:`O(n k log k)` in average, for n words of length at most k.
:math:`O(n^2 k log k)` in worst case due to the usage of a dictionary.
"""
d = {} # maps s to list of words with signature s
for word in S: # group words according to the signature
s = ''.join(sorted(word)) # calculate the signature
if s in d:
d[s].append(word) # append a word to an existing signature
else:
d[s] = [word] # add a new signature and its first word
# -- extract anagrams, ingoring anagram groups of size 1
return [d[s] for s in d if len(d[s]) > 1]
# snip}