Aron
BAN USERHere's my solution in C#.
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
string s1 = "xyz";
string s2 = "xz";
bool result = check(s1, s2);
Console.WriteLine(result);
}
public static bool check(string s1, string s2)
{
//if they're the same, then we just return false
if (s1 == s2) return false;
//get the difference in length between the two
int lenDif = Math.Abs(s1.Length - s2.Length);
//length can only be at most one off
if (lenDif > 1) return false;
//if there's no dif in length, then it's an update
if (lenDif == 0)
{
bool swapped = false;
//go through chars
for (int i = 0; i < s1.Length; i++)
{
//if the chars don't match
if (s1[i] != s2[i])
{
//if we already did a swap,
//then two swaps means they're more than one edit apart
if (swapped) return false;
else swapped = true;
}
}
return true;
}
else //length is dif by 1 (insert/delete)
{
//which one is bigger?
//insert is the reverse of delete, so we can just check for delete
if (s1.Length > s2.Length) return checkDelete(s1, s2);
else return checkDelete(s2, s1);
}
}
private static bool checkDelete(string strLong, string strShort)
{
//create a "buffer" so we can compare permutations
char[] buffer = new char[strShort.Length];
for (int del = 0; del < strLong.Length; del++)
{
int writeIndex = 0;
for (int i = 0; i < strLong.Length; i++)
{
if (i == del) continue;
buffer[writeIndex] = strLong[i];
writeIndex++;
}
if (new String(buffer) == strShort) return true;
}
return false;
}
}
}
I think your answer is close.
- Aron November 04, 2014My step 3 was different:
(3) Iterate through the segments (from segments with most intersections to fewest) and remove them until there are no longer any intersections.