15,799,186 members
Articles / Programming Languages / C#

# Really Simple Anagram Solver

Rate me:
9 Sep 2011CPOL1 min read 35.5K   662   6   5
One really simple anagram solver using recursion.

## Introduction

I will be back! This is my first post since 5 years ago! If you have been interviewed by Microsoft before, you might have come across this kind of recursive questions. I have written a few different solutions, and this is so far my latest, and maybe the smallest one.

## Background

Always good to get your mind juggled a little bit. If you are in the middle of a Tech Access for a job, hope it can help and good luck!

## Using the Code

If you have VS2010, you will know how to run this project. Here is the recursive method:

C#
```static void GenerateAnagram(IList<string> result, string prefix, string src)
{
if (src.Length == 0)
{
return;
}

for (int i = 0; i < src.Length; i++ )
{
string tempPrefix = src[i].ToString();
string newSrc = src.Substring(0, i) + src.Substring(i + 1);
var temp = new List<string>();
GenerateAnagram(temp, tempPrefix, newSrc);
foreach (var s in temp)
{
}
}
}```

And here is how to call it:

C#
```var result = new List<string>();
GenerateAnagram(result, "", "ABC");```

And after one of my reader pointed out the memory problem, here is another approach using recursion:

C#
```static IEnumerable<string> GenerateAnagramAlt(string src)
{
if (src.Length == 0) yield break;
if (src.Length == 1) yield return src;

foreach (string rest in GenerateAnagramAlt(src.Substring(1)))
{
for (int i = 0; i < src.Length; i++)
{
string temp = rest.Substring(0, i) + src[0] + rest.Substring(i);
yield return temp;
}
}
}```

I prefer this one as it doesn't have the memory limitation and nearly twice faster when n >= 9 characters. I like its `IEnumberable` syntax as well! I have updated a new project to include the source file. Thanks goes to my friend ajasin1, who came up with this.

## Points of Interest

I have not included logic to filter duplicated cases, as it can be done using LINQ quite easily.

## History

• 08-09-2011: First posted.
• 09-09-2011: 2.0 posted for `GenerateAnagramAlt`.

Written By
Software Developer (Senior) www.wonga.com
Ireland
I have over 13 Years IT industry experience as Principle/Senior Programmer. I am experienced in .NET/J2EE system design and detailed implementation. I master UML modelling and OO design methodology with a strong C#/C++/Java coding background. I have been in working/managing a distributed project using Agile/Waterfall approach. My business knowledge includes Telecommunication, Financial Investment/Trading, and Banking.

 First Prev Next
 My vote of 2 BitcoinTycoon13-Sep-11 8:30 BitcoinTycoon 13-Sep-11 8:30
 Quickly Out of Memory GenJerDan8-Sep-11 7:05 GenJerDan 8-Sep-11 7:05
 Re: Quickly Out of Memory Ziming8-Sep-11 10:00 Ziming 8-Sep-11 10:00
 Oh no! I never mean this code is production worthy. If you can come up a fix for memory leak, please post it on. Simple is the best.
 Re: Quickly Out of Memory GenJerDan8-Sep-11 10:07 GenJerDan 8-Sep-11 10:07
 Re: Quickly Out of Memory Ziming8-Sep-11 11:03 Ziming 8-Sep-11 11:03
 Last Visit: 31-Dec-99 19:00     Last Update: 11-Dec-23 6:44 Refresh 1