Anagram MethodImplement an anagram solving method that can compute the anagrams of any string.
This page was last reviewed on May 21, 2023.
Anagram. Anagrams can be rearranged to form different words. We can use Dictionary and hash lookups to compute anagram lists quickly.
Some uses. This is useful for learning or making word games. Here we implement an anagram algorithm in the C# language. It is not optimal.
Intro. When you have two words that are anagrams, their alphabetized forms will be equal. Frequencies are equal for each letter. This relationship forms the base of our solution.
cat -> act tca -> act senators -> aeonrsst treasons -> aeonrsst
Example. Here we see a console C# program that first reads in a local word list and then sorts each word. It then stores all the original words separately at that alphabetized key.
Detail We read in the word list. The word list used here is a version of the ENABLE word list available online.
Next For each line, it alphabetizes the letters. This forms the alphabetized key for that word.
Alphabetize String
Detail We look up the key in the Dictionary. If the alphabetized key is found, we append the current word.
And In this way, we hash all real words at keys of their alphabetized forms. We can instantly retrieve the real words.
using System; using System.Collections.Generic; using System.IO; class Anagrams { static void Main() { // Read and sort dictionary. var d = Read(); // Read in user input and show anagrams. string line; while ((line = Console.ReadLine()) != null) { Show(d, line); } } static Dictionary<string, string> Read() { var d = new Dictionary<string, string>(); // Read each line. using (StreamReader r = new StreamReader("enable1.txt")) { string line; while ((line = r.ReadLine()) != null) { // Alphabetize the line for the key. // ... Then add to the value string. string a = Alphabetize(line); string v; if (d.TryGetValue(a, out v)) { d[a] = v + "," + line; } else { d.Add(a, line); } } } return d; } static string Alphabetize(string s) { // Convert to char array, then sort and return. char[] a = s.ToCharArray(); Array.Sort(a); return new string(a); } static void Show(Dictionary<string, string> d, string w) { // Write value for alphabetized word. string v; if (d.TryGetValue(Alphabetize(w), out v)) { Console.WriteLine(v); } else { Console.WriteLine("-"); } } }
martian,tamarin opts,post,pots,spot,stop,tops assentor,senators,starnose,treasons
Discussion. We can use a simple string value type and append new strings to it. This means the data is stored as a single string. Alternatively, we could store the values as a List.
Performance, notes. I altered the code so that it uses Lists instead of strings values. It was faster to use the simpler string value than a List.
Also For better performance, you can persist the alphabetized key-value pairs to the disk. Using a binary file would also help.
Convert Dictionary, String
Summary. We saw how to alphabetize words with Array.Sort and the new string constructor, and then hash those keys in a Dictionary. We implemented a C# anagram algorithm.
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.