这两个edit distance的code# JobHunting - 待字闺中
g*j
1 楼
哪个大侠帮我看看下面这两个edit distance的code，三个操作，add, delete, and
replacement.
为啥第二个code用test case测试的时候总是错的？
int editDistance(char a[], int sizea, char b[], int sizeb) {
if(sizea < 0 || sizeb < 0 || a == NULL || b == NULL ) return -1;
if(sizea == 0 ) return sizeb;
if(sizeb == 0 ) return sizea;
if(a[sizea-1] == b[sizeb -1])
return editDistance(a, sizea - 1, b, sizeb - 1);
else
return min(min(editDistance(a, sizea, b, sizeb - 1) + 1, //delete
editDistance(a, sizea-1, b, sizeb) +1), //add
editDistance(a, sizea -1, b,sizeb-1) +1 //replace
);
}
int editDistance2(char a[], int sizea, char b[], int sizeb) {
if(sizea < 0 || sizeb < 0 || a == NULL || b == NULL ) return -1;
if(sizea == 0 ) return sizeb;
if(sizeb == 0 ) return sizea;
return min(min(editDistance2(a, sizea - 1, b, sizeb) + 1,
editDistance2(a, sizea, b, sizeb - 1) + 1 ),
editDistance2(a, sizea - 1, b, sizeb -1 ) + a[sizea-1]==b
[sizeb-1]? 0:1);
}
replacement.
为啥第二个code用test case测试的时候总是错的？
int editDistance(char a[], int sizea, char b[], int sizeb) {
if(sizea < 0 || sizeb < 0 || a == NULL || b == NULL ) return -1;
if(sizea == 0 ) return sizeb;
if(sizeb == 0 ) return sizea;
if(a[sizea-1] == b[sizeb -1])
return editDistance(a, sizea - 1, b, sizeb - 1);
else
return min(min(editDistance(a, sizea, b, sizeb - 1) + 1, //delete
editDistance(a, sizea-1, b, sizeb) +1), //add
editDistance(a, sizea -1, b,sizeb-1) +1 //replace
);
}
int editDistance2(char a[], int sizea, char b[], int sizeb) {
if(sizea < 0 || sizeb < 0 || a == NULL || b == NULL ) return -1;
if(sizea == 0 ) return sizeb;
if(sizeb == 0 ) return sizea;
return min(min(editDistance2(a, sizea - 1, b, sizeb) + 1,
editDistance2(a, sizea, b, sizeb - 1) + 1 ),
editDistance2(a, sizea - 1, b, sizeb -1 ) + a[sizea-1]==b
[sizeb-1]? 0:1);
}
