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}