Java Anagram Example: HashMap and ArrayList

This Java program uses a word list to generate all anagrams for a given word. It uses sorted strings as keys in a HashMap.
Anagram. An anagram of "tops" is "spot." We rearrange the letters in a key (the word) to get other words. For computer program, we can alphabetize letters to generate a key from words.
With the alphabetized key, we can store an ArrayList of words in a HashMap. The key is an alphabetized pattern, and the values are the original words.
Example program. This program reads in a word file. Please find a file containing many words—some can be downloaded from the Internet, and some computers have them built-in.

GetSortedLine: This method takes the characters in a string and sorts them with Arrays.sort. It returns a new string—it generates keys.

Arrays

ListAnagramsFor: This accesses the HashMap and sees if an ArrayList of original words exists. It prints all anagrams for a certain string.

Main: Reads in the text file of words. We generate sort keys and build up the HashMap data structure.

Java program that finds anagrams import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; public class Program { static HashMap<String, ArrayList<String>> _map; static String getSortedLine(String line) { // Get letters and sort them. char[] letters = line.toCharArray(); Arrays.sort(letters); return new String(letters); } static void listAnagramsFor(String word) { // Sort the letters. String sortedLetters = getSortedLine(word); // Get list from the sorted key in the HashMap. if (_map.containsKey(sortedLetters)) { ArrayList<String> list = _map.get(sortedLetters); // Display items. for (String item : list) { System.out.println(item); } } } public static void main(String[] args) throws IOException { _map = new HashMap<String, ArrayList<String>>(); // Read words file. BufferedReader reader = new BufferedReader( new FileReader("C:\\enable1.txt")); // Read all lines. while (true) { String line = reader.readLine(); if (line == null) { break; } // Get sorted line. String sortedLine = getSortedLine(line); // Add line with the sorted key to the HashMap. // ... Each value is an ArrayList. if (_map.containsKey(sortedLine)) { _map.get(sortedLine).add(line); } else { // Create new ArrayList at key. ArrayList<String> list = new ArrayList<>(); list.add(line); _map.put(sortedLine, list); } } // Close file. reader.close(); // Get anagrams. System.out.println("Anagrams for senator:"); listAnagramsFor("senator"); } } Output Anagrams for senator: atoners senator treason
Notes, performance. With a sorted key, we can access anagrams instantly—only one lookup in a data structure is needed. But the data structure is slower to build up.

And: The HashMap uses more memory. For the lowest-memory approach, we could test a string against all words in the original file.

HashMap

Further: A tree like a DAG that stores each letter would provide optimal performance for this operation, but is more complex.

Tree
Notes, Knuth. Anagrams are not that useful in real-world programs. But even Donald Knuth in The Art of Computer Programming uses anagrams to explore algorithms.

So: Anagrams are a useful exercise. The Java program here is not optimal—see if you can improve it.

A summary. Sorting is a transformation function—it builds a unique hash for the keys. Letter frequencies are retained. With sorting, we find anagrams from a HashMap.
© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
HomeSearch
Home
Dot Net Perls