CMUWaffles
BAN USERThis solution seems easiest to me since it is iterative instead of recursive and it is still o(nlogn):
Create new empty list sortedItems. Iterate from the back of the original list to the front. Insert the array item into the sortedItems list in SORTED ORDER. Then, the number of unordered pairs for that item will be (sortedItems.Length - 1) - P, where P is the position in the List where the sorted item was inserted. Add this to the total sum of unordered pairs. There are N items in the original list and each insertion costs log(n) so the total cost is Nlog(N)
static void Main(string[] args)
{
string string1 = "xyzkqow";
string string2 = "xyzbkqow";
Console.WriteLine("String1 is " + string1 + ", and 2 is " + string2);
int i1 = 0;
int i2 = 0;
int j1 = string1.Length - 1;
int j2 = string2.Length - 1;
int lengthDiff = Math.Abs(j1 - j2);
if (lengthDiff > 1)
{
Console.WriteLine("FAIL: String Lengths are too different");
return;
}
bool mismatch = false;
// search forward
while (i1 < string1.Length && i2 < string2.Length)
{
if (string1[i1] == string2[i2])
{
i1++;
i2++;
continue;
}
mismatch = true;
break;
}
if (!mismatch) {
if (string1.CompareTo(string2) == 0)
{
Console.WriteLine("FAIL: They are exactly the same");
return;
}
System.Console.WriteLine("PASS: They are off by one character at the end");
return;
}
mismatch = false;
//search backward up until the first mismatch we found
while (j1 != i1 && j2 != i2)
{
if(string1[j1] == string2[j2])
{
j1--;
j2--;
continue;
}
mismatch = true;
break;
}
if (!mismatch)
{
System.Console.WriteLine("PASS: Only one mismatch");
}
else
{
Console.WriteLine("FAIL: More than one mismatch");
}
}
Good catch.
I modified the condition of the second loop to be:
That should fix it i I think
- CMUWaffles November 04, 2014