Anagram Solver

I was coding out a simple string permuting function and I thought of writing out an AnagramSolver just for completion.

The Dictionary can be provided as a wordlist in the form of a text file with a word string per line. You can find several word lists here: http://wordlist.sourceforge.net/


//Sources
#include<iostream>
#include<string>
#include<fstream>
#include<map>

using namespace std;
class AnagramChecker
{
public:
map<string, bool> Dictionary;
map<string, bool> ResultList;

//Recursive string permuter
void RecurveStrPerm(string Buffer, string Test, int Cur)
{
 if (Cur >= Test.length())
 {
 if (Dictionary.count(Buffer) > 0)
 if (ResultList.count(Buffer) == 0)
 ResultList[Buffer] = true;
 return;
 }

for(int i = 0; i <= Buffer.length(); i++)
 {
 Buffer.insert(i, 1, Test[Cur]);
 RecurveStrPerm(Buffer, Test, Cur + 1);
 Buffer.erase(i, 1);
 }
}

//Build a table out of the strings
void BuildInMemDic()
{
 Dictionary.clear();
 ifstream DicReader;
 DicReader.open("WordList.txt");
 string CurrentWord= "";
 while (!DicReader.eof())
 {
 getline(DicReader, CurrentWord);
 for (int i = 0; i < CurrentWord.length(); i++)
 CurrentWord[i] = tolower(CurrentWord[i]);
 Dictionary[CurrentWord] = true;

 }
 DicReader.close();
}

//Get Result
void GetResult()
{
 cout << "\nAnagrams: \n";
 for (map<string, bool>::iterator ResultListPtr = ResultList.begin(); ResultListPtr != ResultList.end(); ResultListPtr++)
 cout << "\n" << ResultListPtr->first;

}

public:

AnagramChecker()
 {
 BuildInMemDic();
 }

void Find(string Test)
 {
 ResultList.clear();
 int cur = 0, n = Test.length();
 RecurveStrPerm("", Test, 0);
 GetResult();
 }

};

void main()
{
 string Test = "Slate";
 cout << "\nBuilding In memory Dictionary...";
 AnagramChecker AnaObj;
 cout << "\n\nInmemory dictionary built!...\n\n";

char ExitChoice = 'n';
 while (ExitChoice!='y')
 {
 cout << "\n\nEnter Anagram: ";
 cin >> Test;
 for (int i = 0; i < Test.length(); i++)
 Test[i] = tolower(Test[i]);

cout << "\n\nAnagrams for " << Test << ":\n\n";
 AnaObj.Find(Test);
 cout << "\n\nDo you want to continue: y /n :";
 cin >> ExitChoice;

 }
 cout << "\nEnd of code\n";
 system("pause");
 return;
}

The code is NOT optimized. It can be sped up with simple multi-threading, but I have let go of those for simplicity.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s