问个字符串距离的问题# JobHunting - 待字闺中
s*g
1 楼
就是那个经典的比较两个字符串距离的问题，看两个字符串需要多少步变换才能成为相
同的字符串。我用递归写的，可是死活不对。谁给指点一下问题在哪儿？
这是我的C# code:
public int CalcDistance(string src, int srcBegin, int srcEnd, string
dst, int dstBegin, int dstEnd)
{
if (srcBegin > srcEnd)
{
if (dstBegin > dstEnd)
return 0;
else
return dstEnd - dstBegin + 1;
}
if (dstBegin > dstEnd)
{
if (srcBegin > srcEnd)
return 0;
else
return srcEnd - srcBegin + 1;
}
if (src[srcBegin] == dst[dstBegin])
return CalcDistance(src, srcBegin + 1, srcEnd, dst, dstBegin
+ 1, dstEnd);
else
{
int dist1 = CalcDistance(src, srcBegin + 1, srcEnd, dst,
dstBegin + 2, dstEnd);
int dist2 = CalcDistance(src, srcBegin + 2, srcEnd, dst,
dstBegin + 1, dstEnd);
int dist3 = CalcDistance(src, srcBegin + 2, srcEnd, dst,
dstBegin + 2, dstEnd);
return MinOfThree(dist1, dist2, dist3) + 1;
}
调用的时候：
static void Main(string[] args)
{
StringDistance std = new StringDistance();
string src = "source";
string dst = "destination";
int dist = std.CalcDistance(src, 0, src.Length-1, dst, 0, dst.
Length-1);
Console.WriteLine("Distance between {0} and {1} is {2}", src,
dst, dist);
Console.ReadKey();
}
结果我死活打印出来的distance是6，而不是10。肯定是前面递归的某个地方错了，但
是我debug进去半天也没figureout。
同的字符串。我用递归写的，可是死活不对。谁给指点一下问题在哪儿？
这是我的C# code:
public int CalcDistance(string src, int srcBegin, int srcEnd, string
dst, int dstBegin, int dstEnd)
{
if (srcBegin > srcEnd)
{
if (dstBegin > dstEnd)
return 0;
else
return dstEnd - dstBegin + 1;
}
if (dstBegin > dstEnd)
{
if (srcBegin > srcEnd)
return 0;
else
return srcEnd - srcBegin + 1;
}
if (src[srcBegin] == dst[dstBegin])
return CalcDistance(src, srcBegin + 1, srcEnd, dst, dstBegin
+ 1, dstEnd);
else
{
int dist1 = CalcDistance(src, srcBegin + 1, srcEnd, dst,
dstBegin + 2, dstEnd);
int dist2 = CalcDistance(src, srcBegin + 2, srcEnd, dst,
dstBegin + 1, dstEnd);
int dist3 = CalcDistance(src, srcBegin + 2, srcEnd, dst,
dstBegin + 2, dstEnd);
return MinOfThree(dist1, dist2, dist3) + 1;
}
调用的时候：
static void Main(string[] args)
{
StringDistance std = new StringDistance();
string src = "source";
string dst = "destination";
int dist = std.CalcDistance(src, 0, src.Length-1, dst, 0, dst.
Length-1);
Console.WriteLine("Distance between {0} and {1} is {2}", src,
dst, dist);
Console.ReadKey();
}
结果我死活打印出来的distance是6，而不是10。肯定是前面递归的某个地方错了，但
是我debug进去半天也没figureout。
