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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谁面试写这种code我绝对把他干掉。就算是中国人都不手软的。
| e***s 发帖数: 799 | | e***s 发帖数: 799 | | d*********g 发帖数: 154 | 7
求教,是因为这个递归重复计算太多了么?
【在 a********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谁面试写这种code我绝对把他干掉。就算是中国人都不手软的。
| y********f 发帖数: 1 | 8 Test Case没错吧,是time limit exceed吧,复杂度太高了,成指数了吧,用DP就好了
,思路类似,加个初始化就好了。 |
|