WildCard Matching algorithm

The logic is quite simple. We do the following 3 basic checks before we do the comparison:

1. Check for nulls and return if either of the String or Pattern is null


2. Check if we have reached the end of string. If so, return true


3. If either of string or pattern are left over, return false


4. One case that we need to explicitly handle is when string is EMPTY and pattern is made solely of one or more *s.

Comparison:

1. If it is a char or ?, skip 1 ahead in both string and pattern


2. If it is a *, return the result of
   
   
   
   • string+1,pattern+1 - For handling multiple *s
   
   
   • string,pattern+1     - For handling null *
   
   
   • string+1,pattern     - For handling multi-char *
   
   
   
   

The actual code is pretty simple. The following code has a complexity of around 2^n for an sized string.

[code language="cpp"]
bool OnlyAskterisk(char* Pattern)
{
if (*Pattern == '\0') return true;
if (*Pattern != '*') return false;
else return OnlyAskterisk(Pattern + 1);
}

bool isMatch(char *String, char *Pattern)
{
//Base case checks
if (*String=='\0' &&OnlyAskterisk(Pattern)) return true;
if (!String || !Pattern) return false;
if (*String == '\0' && *Pattern == '\0') return true;
if (*String == '\0' || *Pattern == '\0') return false; //Tricky case which is used to eliminate stack overflows with * variable

//Actual comparisons
if ((*String == *Pattern) || (*Pattern == '?'))
return isMatch(String + 1, Pattern + 1);
//Multimatch- StringMoves, No Match-PatternMoves SingleMatch- BothMove. Single match is to handle last char being *
if (*Pattern == '*') return (isMatch(String + 1, Pattern) || isMatch(String + 1, Pattern + 1) || isMatch(String, Pattern + 1));
return false;
}

[/code]

Hash Table in C++

I have implemented a simple hash-table in C++. I have used the modified version of Bernstein's Hash function for it. For more on the Bernstein's hash, read this http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

 

 

[code language="cpp"]</pre>
class HashTable
{
typedef long long unsigned int HashValueType;
typedef int KeyType;
int BucketSize;
vector<vector<KeyType>> Buckets;

void InsertAtBucket(int ValueParam, int BucketId)
{
Buckets[BucketId].push_back(ValueParam);
}
bool FindAtBucket(int ValueParam, int BucketId)
{
if (Buckets[BucketId].size() <= 0) return false;
vector<KeyType>::iterator Ptr = Buckets[BucketId].begin();
while (Ptr != Buckets[BucketId].end())
{
if ((*Ptr) == ValueParam) return true;
Ptr++;
}
return false;
}
HashValueType HashFunction(void* Input, int Size)
{
HashValueType HValue = 0;
for (int i = 0; i < Size; i++)
HValue = (33 * HValue) + ((char*)Input)[i];
return HValue;;
}
public:

HashTable(int BucketSizeParam = 100)
{
BucketSize = BucketSizeParam;
Buckets.clear();
for (int i = 0; i < BucketSize; i++)
Buckets.push_back(vector<KeyType>());
}
void Insert(int ValueParam)
{
//BucketSize
if (!LookUp(ValueParam))
InsertAtBucket(ValueParam, HashFunction(&ValueParam,sizeof(int))%BucketSize);
}

bool LookUp(int ValueParam)
{
return FindAtBucket(ValueParam, HashFunction(&ValueParam, sizeof(int))%BucketSize);
}
};
<pre>
[/code]

Priority Queue implementation using MaxHeap

The Priority Queue with a MaxRemove() interface can be implemented using a MaxHeap which is a complete binary tree that maintains the maximum (here it would be the maximum of the priority values) of the elements that it contains at its root.

The Code is super simple and is as follows:

[code language="cpp"]

PriorityQueue(int CapacityParam)
{
Data = (int*)malloc(CapacityParam*sizeof(int));
ToH = -1;
Capacity = CapacityParam;
}

void Display()
{
cout << "\nList:\n";
for (int iter = 0; iter <= ToH; iter++)
cout << " " << Data[iter];
}

void HeapifyUp(int Position)
{
if (Position < 1) return;
if (Data[Position]>Data[(Position - 1) / 2])
{
Swap(&(Data[Position]), &(Data[(Position - 1) / 2]));
HeapifyUp((Position - 1) / 2);
}
}

bool Insert(int ParamValue)
{
if (ToH >= Capacity - 1) return false; //QueueOverflow
Data[++ToH] = ParamValue;
HeapifyUp(ToH);
return true;
}

void HeapifyDown(int Position)
{
if (2 * Position + 1 > ToH) return;
if (2 * Position + 2 <= ToH)
{
//LR exists
if (Data[2 * Position + 1] > Data[2 * Position + 2])
{
//L
if (Data[2 * Position + 1] > Data[Position]) Swap(&(Data[2 * Position + 1]) ,& (Data[Position]));
HeapifyDown(2 * Position + 1);
}
else
{
//R
if (Data[2 * Position + 2] > Data[Position]) Swap(&(Data[2*Position+2]), &(Data[Position]));
HeapifyDown(2 * Position + 2);
}
}
else
{
//Only L exists
//L
if (Data[2 * Position + 1] > Data[Position]) Swap(&(Data[2 * Position + 1]), &(Data[Position]));
HeapifyDown(2 * Position + 1);
}
}

void SortDump()
{
int SortToH = ToH;
while (ToH >= 0)
{
Swap(&(Data[0]), &(Data[ToH]));
--ToH;
HeapifyDown(0);
}
ToH = SortToH;
Display();
}
};

void FillArrayWithRand(int *Array, int Size)
{
if (!Array || Size<=0) return;
for (int i = 0; i < Size; i++)
Array[i] = (rand() % 10);
}
int main()
{
//Dont allow 0 in the tree for CommonAncestor problem

const int DataSetSize = 9999;
int *RandArray = (int*)malloc(DataSetSize * sizeof(int));
FillArrayWithRand(RandArray, DataSetSize);
cout << "\nRandom Array:\n";
for (int i = 0; i < DataSetSize; i++)
cout<<" "<<RandArray[i];

PriorityQueue test(DataSetSize);
for (int i = 0; i < DataSetSize; i++)
test.Insert( RandArray[i]);
test.Display();
test.SortDump();

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

return 0;
}

&nbsp;

[/code]