s********g
发帖数: 29 | 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。 | p*****2
发帖数: 21240 | | z*********8
发帖数: 2070 | 3 是啊， 画个大matrix， 代码十行就够了吧
【在 p*****2 的大作中提到】
: 能不能说说思路？
: 这题难道不应该用DP吗？
| s********g
发帖数: 29 | 4 基本的思想是这样的：
1）如果src和dst+1相等，那么distance就是1
2）如果src+1和dst相等，那么distance就是1
3）如果src+1和dst+1相等，那么distance也是1
这样就可以反复递归了...
【在 p*****2 的大作中提到】
: 能不能说说思路？
: 这题难道不应该用DP吗？
| p*****2
发帖数: 21240 | 5
这几个逻辑怎么来的？
1相当于b＋1？
2相当于a+1?
3相当于什么？
【在 s********g 的大作中提到】
: 基本的思想是这样的：
: 1）如果src和dst+1相等，那么distance就是1
: 2）如果src+1和dst相等，那么distance就是1
: 3）如果src+1和dst+1相等，那么distance也是1
: 这样就可以反复递归了...
| r*****e
发帖数: 792 | 6 the problem in your code should be corrected as:
(1,0) (0,1) (1,1) instead of (1,2)(2,1), (2,2)
you cannot jump 2 chars when the 0's chars don't match.
string
【在 s********g 的大作中提到】
: 就是那个经典的比较两个字符串距离的问题，看两个字符串需要多少步变换才能成为相
: 同的字符串。我用递归写的，可是死活不对。谁给指点一下问题在哪儿？
: 这是我的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;
| t*********7
发帖数: 255 | 7 就是找最大公共字串吧...反正不论加减修改都算一次... | y****n
发帖数: 743 | | p*****2
发帖数: 21240 | 9
edit distance.
就是两个字符串a，b。
从a变到b需要最小的步骤
每步可以做三种操作
1. 增加一个字符
2. 删除一个字符
3. 修改一个字符
【在 y****n 的大作中提到】
: 能把原题原文贴出来吗？
| b******t
发帖数: 965 | 10 en
wikipedia上有解答
【在 p*****2 的大作中提到】
:
: edit distance.
: 就是两个字符串a，b。
: 从a变到b需要最小的步骤
: 每步可以做三种操作
: 1. 增加一个字符
: 2. 删除一个字符
: 3. 修改一个字符
| l*******s
发帖数: 1258 | 11 请google： edit distance
这个是DP的经典问题，思路挺NB的，非常具有扩展性。相关算法在NLP领域用的很多。
基本思路就是用两个字符串构建一个matrix，每个cell代表对应的两个字串的edit
distance。
自己定义insert、delete、alternate的cost，然后比较每个cell周围三个cell的值，
确定当前值，然后就ok了 |
|
