Java Anagram Example: HashMap and ArrayList

Use a word list to generate all anagrams for a given word. Use 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.

Array

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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Java Anagram Example: HashMap and ArrayList

Related Links:

.Net

Java

Related Links