Click here to Skip to main content
Click here to Skip to main content

Really Simple Anagram Solver

, 9 Sep 2011
Rate this:
Please Sign up or sign in to vote.
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:

static void GenerateAnagram(IList<string> result, string prefix, string src)
{
    if (src.Length == 0)
    {
        result.Add(prefix);
        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)
        {
            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[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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Ziming
Software Developer (Senior) www.wonga.com
Ireland 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.

Comments and Discussions

 
GeneralMy vote of 2 PinmemberFathomSavvy13-Sep-11 7:30 
QuestionQuickly Out of Memory PinmemberGenJerDan8-Sep-11 6:05 
AnswerRe: Quickly Out of Memory PinmemberZiming8-Sep-11 9:00 
GeneralRe: Quickly Out of Memory PinmemberGenJerDan8-Sep-11 9:07 
GeneralRe: Quickly Out of Memory PinmemberZiming8-Sep-11 10:03 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140721.1 | Last Updated 9 Sep 2011
Article Copyright 2011 by Ziming
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid