一道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道题

一道题# JobHunting - 待字闺中

c*r2012-12-01 08:12

1 楼

Find the minimum edit distance between two strings

b*m2012-12-01 08:12

2 楼

标准递归题。

【在 c********r 的大作中提到】

: Find the minimum edit distance between two strings

b*m2012-12-01 08:12

3 楼

随便写了一下，请大家指正：
int EditDistance(char *s1, char *s2)
{
if( !s1 || !*s1 ) return strlen(s2);
if( !s2 || !*s2 ) return strlen(s1);

return min3(
EditDistance(s1 + 1, s2) + 1,
EditDistance(s1, s2 + 1) + 1,
EditDistance(s1 + 1, s2 + 1) + (*s1 == *s2 ? 0 : 1)
);
}

l*82012-12-01 08:12

4 楼

这是指数级时间复杂度吧。用dp好些

【在 b***m 的大作中提到】

: 随便写了一下，请大家指正：
: int EditDistance(char *s1, char *s2)
: {
: if( !s1 || !*s1 ) return strlen(s2);
: if( !s2 || !*s2 ) return strlen(s1);
:
: return min3(
: EditDistance(s1 + 1, s2) + 1,
: EditDistance(s1, s2 + 1) + 1,
: EditDistance(s1 + 1, s2 + 1) + (*s1 == *s2 ? 0 : 1)

c*r2012-12-01 08:12

5 楼

好猫兄，可否简单讲一下思路

【在 b***m 的大作中提到】

c*r2012-12-01 08:12

6 楼

简单说说思路

【在 l*********8 的大作中提到】

: 这是指数级时间复杂度吧。用dp好些

b*m2012-12-01 08:12

7 楼

俺不会DP，正打算向二爷讨教。

【在 l*********8 的大作中提到】

: 这是指数级时间复杂度吧。用dp好些

j*s2012-12-01 08:12

8 楼

用DP好一些
for(int i = 1 ; i< n1 + 1; ++i){
for (int j = 1; j < n2 + 1; ++j){
if (word1[i - 1] == word2[j - 1])
{
dist[i][j] = dist[i - 1][j - 1];
}
else{
dist[i][j] = min(dist[i - 1][j - 1], dist[i - 1][j],
dist[i][j - 1]) + 1;
}
}
}