C# Anagram Method

Implement an anagram solving method that can compute the anagrams of any string.

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.

Input string/alphabetized form: 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.StreamReader TryGetValue ToCharArray Array.Sort

Main: 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

Dictionary: We look up the key in the Dictionary. If the alphabetized key is found, we append the current word.

Dictionary

And: In this way, we hash all real words at keys of their alphabetized forms. We can instantly retrieve the real words.

C# program that finds anagrams in file 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("-"); } } } Output 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.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

Notes, Scrabble. In the game Scrabble, blanks substitute for any letter. This can be handled in different ways in an anagram program: with a tree or approximate string matching.Tree

Also: You can use Levenshtein distance to find similar strings. But it is not helpful in Scrabble.

Levenshtein

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.

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

C# Anagram Method

Related Links:

.Net

Java

Related Links