This notebook was prepared by Donne Martin. Source and license info is on GitHub.
Input: ['ram', 'act', 'arm', 'bat', 'cat', 'tab'] Sort the chars for each item: 'ram' -> 'amr' 'act' -> 'act' 'arm' -> 'amr' 'abt' -> 'bat' 'cat' -> 'act' 'abt' -> 'tab' Use a map of sorted chars to each item to group anagrams: { 'amr': ['ram', 'arm'], 'act': ['act', 'cat'], 'abt': ['bat', 'tab'] } Result: ['arm', 'ram', 'act', 'cat', 'bat', 'tab']
Complexity:
from collections import OrderedDict
class Anagram(object):
def group_anagrams(self, items):
if items is None:
raise TypeError('items cannot be None')
if not items:
return items
anagram_map = OrderedDict()
for item in items:
# Use a tuple, which is hashable and
# serves as the key in anagram_map
sorted_chars = tuple(sorted(item))
if sorted_chars in anagram_map:
anagram_map[sorted_chars].append(item)
else:
anagram_map[sorted_chars] = [item]
result = []
for value in anagram_map.values():
result.extend(value)
return result
%%writefile test_anagrams.py
import unittest
class TestAnagrams(unittest.TestCase):
def test_group_anagrams(self):
anagram = Anagram()
self.assertRaises(TypeError, anagram.group_anagrams, None)
data = ['ram', 'act', 'arm', 'bat', 'cat', 'tab']
expected = ['ram', 'arm', 'act', 'cat', 'bat', 'tab']
self.assertEqual(anagram.group_anagrams(data), expected)
print('Success: test_group_anagrams')
def main():
test = TestAnagrams()
test.test_group_anagrams()
if __name__ == '__main__':
main()
Overwriting test_anagrams.py
%run -i test_anagrams.py
Success: test_group_anagrams