g***j
发帖数: 1275 | 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);
} | h****n
发帖数: 362 | 2 editDistance2(a, sizea - 1, b, sizeb -1 ) + （a[sizea-1]==b
[sizeb-1]? 0:1)）; | a********e
发帖数: 15 | 3 谁面试写这种code我绝对把他干掉。就算是中国人都不手软的。 | g*********e
发帖数: 14401 | 4
你拽什么拽，这扣得很烂吗？
【在 a********e 的大作中提到】
: 谁面试写这种code我绝对把他干掉。就算是中国人都不手软的。
| e***s
发帖数: 799 | | e***s
发帖数: 799 | | d*********g
发帖数: 154 | 7
求教，是因为这个递归重复计算太多了么？
【在 a********e 的大作中提到】
: 谁面试写这种code我绝对把他干掉。就算是中国人都不手软的。
| y********f
发帖数: 1 | 8 Test Case没错吧，是time limit exceed吧，复杂度太高了，成指数了吧，用DP就好了
，思路类似，加个初始化就好了。 |
|
