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.
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:
static void GenerateAnagram(IList<string> result, string prefix, string src)
if (src.Length == 0)
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)
result.Add(prefix + s);
And here is how to call it:
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:
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 + 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.
- 08-09-2011: First posted.
- 09-09-2011: 2.0 posted for