AP AB Free Response

Name: AnagramGrouper
Topic: HashSet, HashMap
Reference: 2008 Question 1
Source Code: AnagramGrouper

A key string for a word is the string obtained when the letters in the word are arranged in alphabetical order. For example, the words "poodle" and "looped" both have the key string "deloop". A set of words form an anagram set if all words in the set have the same key string. Some examples of anagram sets include {"poodle", "looped"}, {"nastier", "retains", "retinas"}, and {"discounter", "introduces", "reductions"}.

Consider the problem of creating a group of anagram sets from a list of words. A word with no anagrams in the list will be contained in a singleton set. The example below shows a list of words and the anagram sets that are produced from that list.

Original list of words
[ant, introduces, poodle, tan, looped, discounter, nastier, polled, retains, retinas, reductions]

Anagram sets from the list of words
{tan, ant}
{introduces, reductions, discounter}
{poodle, looped}
{retains, retinas, nastier}
{polled}

The anagram sets will be organized as a map in which each key is a key string and the associated value is the set
of words that each have that key string. The following diagram shows a map with the key strings and associated
anagram sets that would be created from the list in the previous example.

A partial declaration of the AnagramGrouper class is as follows: You will implement two methods in the
AnagramGrouper class. The class contains a private helper method that can be used to create a key string
from a word.

public class AnagramGrouper
{
    // Maps a key string to a corresponding anagram set
    private HashMap <String, HashSet<String>> groups;
    
    /** Constructs a map from words in which the keys are key strings and the
     *   value associated with a key string is the set of anagrams having that key string.
     *   Postcondition: each entry of words is contained in an anagram set
     *   @param words a list of strings to be grouped into anagram sets
     *          Precondition: words.size() > 0
     */
    public AnagramGrouper(List words)
    { /* to be implemented in part (a) */ }
    
    /** @return a set of all anagram sets of largest size in this AnagramGrouper
     */
    public HashSet <HashSet<String>>findLargestSets()
    { /* to be implemented in part (b) */ }
    
    /** @param s a word
     *  @return a string with the same letters as s, arranged in alphabetical order
     */
    private String createKeyString(String s)
    { /* implementation not shown */ }
    
    
    // There may be instance variables, constructors, and methods that are not shown.
}

1. Write the AnagramGrouper constructor. The constructor takes a list of words and constructs a map in
   which each key is a key string and the associated value is the set of words that each have that key string. The
   map should contain all the anagram sets that are generated from the list of words.
   
   Complete the AnagramGrouper constructor below.
   

       /** Constructs a map from words in which the keys are key strings and the
        *   value associated with a key string is the set of anagrams having that key string.
        *   Postcondition: each entry of words is contained in an anagram set
        *   @param words a list of strings to be grouped into anagram sets
        *          Precondition: words.size() > 0
        */
       public AnagramGrouper(List words)
       {
   
   
   
   
       }

2. Write the AnagramGrouper method findLargestSets. This method analyzes the instance
   variable groups and returns a set containing the largest anagram set(s); that is, the set(s) with the most
   elements. In the example shown at the beginning of the question, the method would return a set containing
   the sets {introduces, reductions, discounter} and {retains, retinas, nastier}.
   
   Complete method findLargestSets below.
   

   /** @return a set of all anagram sets of largest size in this AnagramGrouper
    */
    public HashSet <HashSet<String>>findLargestSets()
    { 
   
   
   
   
   
   
    }

Sample Output

cdeinorstu - {reductions, discounter, introduces}
dellop - {polled}
aeinrst - {nastier, retains, retinas}
deloop - {looped, poodle}
ant - {ant, tan}


findLargestSets Test
--------------------
{nastier, retains, retinas}
{reductions, discounter, introduces}


Press any key to continue...