anagrams.py

""" 
Provided with a set of valid words and given an input string, generate all valid words that are anagrams of input.
"""

import collections

class AnagramServer(object):
    def __init__(self, valid_words=None):
        """
        :type valid_words: [<unicode>]
        """
        # Build dictionary mapping word keys (sorted input words) to list of words that are anagrams.
        self._cached_anagrams = collections.defaultdict(list)
        self._precompute_anagrams(valid_words)

    def get_anagrams(self, input_letters):
        """
        :rtype: [<unicode>]
        :return: list of words that are anagrams; empty list if no such words exist
        
        :type input_letters: <unicode>
        """
        anagrams = []
        if input_letters:
            key = self.sort_letters_in_word(input_letters)
            anagrams = self._cached_anagrams.get(key) or []
        return anagrams

    @classmethod
    def sort_letters_in_word(cls, word):
        """Return string that is composed of every letter in provided word in sorted order.
        """
        return ''.join(sorted(word)) if word else word

    def _precompute_anagrams(self, valid_words):
        """Populate self._cached_anagrams.

        Keys are generated by sorting the letters in each valid word.
        Values are lists of words that are anagrams for key.
        
        :type valid_words: set(<unicode>)

        """
        for word in valid_words:
            key = self.sort_letters_in_word(word)
            self._cached_anagrams[key].append(word)


        
if __name__ == '__main__':
    import unittest

    class TestAnagramServer(unittest.TestCase):
        valid_words = set(['eat', 'ate', 'tea', 'team', 'meat', 'mate', 'tame', 'perplex', 'bubble'])

        def _get_server(self):
            return AnagramServer(valid_words=self.valid_words)

        def _sort_word(self, word):
            return ''.join(sorted(word))
            
        def test_init(self):
            """Verify that init precomputes cache.
            """
            server = self._get_server()
            expected_keys = set()
            for valid_word in self.valid_words:
                expected_keys.add(self._sort_word(valid_word))
            self.assertEqual(expected_keys, set(server._cached_anagrams.keys()))

        def test_get_anagrams(self):
            """Verify expected anagrams for self.valid_words.
            """
            server = self._get_server()
            anagram_sets = (set(['eat', 'tea', 'ate']),
                            set(['team', 'meat', 'mate', 'tame']),
                            set(['perplex']),
                            set(['bubble']))
            for anagram_set in anagram_sets:
                for w in anagram_set:
                    self.assertEqual(anagram_set, set(server.get_anagrams(w)))
            
        def test_get_anagrams__no_such_words(self):
            """Verify get_anagrams returns [] when input word has no anagrams that are valid words.
            """
            server = self._get_server()
            self.assertEqual([], server.get_anagrams('anagram'))
            
        def test_sort_letters_in_word(self):
            anagrams = ('abc', 'bca', 'cab', 'acb', 'cba', 'bac')
            key = 'abc'
            for word in anagrams:
                sorted_word = AnagramServer.sort_letters_in_word(word)
                self.assertEqual(key, sorted_word)

        def test_sort_letters_in_word__empty(self):
            for empty in [None, '']:
                self.assertEqual(empty, AnagramServer.sort_letters_in_word(empty))


    # run tests
    unittest.main()