Anagram ExampleUse a word list to generate all anagrams for a given word. Use sorted strings as keys in a HashMap.
This page was last reviewed on May 21, 2023.
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.
Note GetSortedLine() takes the characters in a string and sorts them with Arrays.sort. It returns a new string—it generates keys.
Note 2 ListAnagramsFor accesses the HashMap and sees if an ArrayList of original words exists. It prints all a word's anagrams.
Note 3 Main() reads in the text file of words. We generate sort keys and build up the HashMap data structure.
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"); } }
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.
Further A tree like a DAG that stores each letter would provide optimal performance for this operation, but is more complex.
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.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on May 21, 2023 (simplify).
© 2007-2023 Sam Allen.